`

hud 1175 连连看(dfs)

    博客分类:
  • dfs
阅读更多

连连看

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5387    Accepted Submission(s): 1401

Problem Description
“连连看”相信很多人都玩过。没玩过也没关系,下面我给大家介绍一下游戏规则:在一个棋盘中,放了很多的棋子。如果某两个相同的棋子,可以通过一条线连起来(这条线不能经过其它棋子),而且线的转折次数不超过两次,那么这两个棋子就可以在棋盘上消去。不好意思,由于我以前没有玩过连连看,咨询了同学的意见,连线不能从外面绕过去的,但事实上这是错的。现在已经酿成大祸,就只能将错就错了,连线不能从外围绕过。
玩家鼠标先后点击两块棋子,试图将他们消去,然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

 

Input
输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000),分别表示棋盘的行数与列数。在接下来的n行中,每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子,正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50),表示下面有q次询问。在接下来的q行里,每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时,输入结束。
注意:询问之间无先后关系,都是针对当前状态的!

 

Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

 

Sample Input
3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0

 

Sample Output
YES NO NO NO NO YES
    
        连连看大家都应该玩过吧,如果写一个连连看游戏,就要用到搜索的算法,下面就是这题的解决方法。注意:记得剪枝,不然会超时,你玩连连看游戏不会出现按两个东西要等很久才能消吧,所以剪枝很重要!
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

int n, m, t, k, z;
int x1, y1, x2, y2;
int a[1005][1005];
bool map[1005][1005], flag;

void init()     //初始化函数
{
    flag = false;
    memset(map, false, sizeof(map));
}

void dfs(int x, int y, int z, int k)    //坐标(x,y)
{
    if(flag) return;
    if(x<=0 || y<=0 || x>n || y>m) return;  //若超界,返回
    if(k>=3) return;        //若转弯数已经超过3次,返回
    if(x == x2 && y == y2)
    {
        flag = true;
        return;
    }
    if(k == 2)  //超强剪枝:若已经转两次弯,则目标坐标必须要在前进方向的前面,否则直接返回
    {
        if( !(z==1 && x>x2 && y==y2  ||  z==2 && x<x2 && y==y2
              ||  z==3 && y>y2 && x==x2  ||  z==4 && y<y2 && x==x2) )
            return;
    }
    if(a[x][y] != 0) return;    //如果该点不是0,则不能走,返回
    if(map[x][y]) return;       //如果该点已经走过,返回
    map[x][y] = true;       //标记该点为走过
    if(z == 1)  //上
    {
        dfs(x-1, y, 1, k);
        dfs(x+1, y, 2, k+1);
        dfs(x, y-1, 3, k+1);
        dfs(x, y+1, 4, k+1);
    }
    else if(z == 2) //下
    {
        dfs(x-1, y, 1, k+1);
        dfs(x+1, y, 2, k);
        dfs(x, y-1, 3, k+1);
        dfs(x, y+1, 4, k+1);
    }
    else if(z == 3) //左
    {
        dfs(x-1, y, 1, k+1);
        dfs(x+1, y, 2, k+1);
        dfs(x, y-1, 3, k);
        dfs(x, y+1, 4, k+1);
    }
    else if(z == 4) //右
    {
        dfs(x-1, y, 1, k+1);
        dfs(x+1, y, 2, k+1);
        dfs(x, y-1, 3, k+1);
        dfs(x, y+1, 4, k);
    }
    map[x][y] = false;  //若深搜不成功,标记该点为未走过
}

int main()
{
    int i, j;
    while(scanf("%d %d", &n, &m))
    {
        if(!n && !m) break;
        for(i = 1; i <= n; i++)
            for(j = 1 ; j <= m; j++)
                scanf("%d", &a[i][j]);
        scanf("%d", &t);
        for(i = 0; i < t; i++)
        {
            init();
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            if(x1 == x2 && y1 == y2 && a[x1][y1] != 0) //若两点坐标是相同的,输出NO
                printf("NO\n");
            else if(a[x1][y1] == a[x2][y2] && a[x1][y1] != 0) //若两点的值相同且不为0
            {
                dfs(x1-1, y1, 1, 0);
                dfs(x1+1, y1, 2, 0);
                dfs(x1, y1-1, 3, 0);
                dfs(x1, y1+1, 4, 0);
                if(flag) printf("YES\n");
                else printf("NO\n");
            }
            else printf("NO\n");
        }
    }

    return 0;
}
 
分享到:
评论

相关推荐

    (整理了两个)HUD 设计案例 zemax

    抬头显示(Head-Up Display, 简称HUD)是一种先进的汽车和航空电子设备,它将重要的驾驶信息投射到驾驶员的视线前方,使驾驶员在不转移视线的情况下获取信息,提高驾驶安全性和操作便利性。Zemax是一款强大的光学...

    2022中国汽车智能化功能模块系列研究-HUD篇

    抬头显示系统(HUD)是汽车智能化的一个重要组成部分,它的全称是Head-Up Display。HUD的主要目的是提高驾驶安全性,通过在驾驶员视线范围内显示关键信息,如车速、导航指示、警告信息等,使得驾驶员无需分心查看...

    HUD.zip_hud_hud osg_hud 开发_osg

    标题"HUD.zip_hud_hud osg_hud 开发_osg"暗示了这是一个关于OSG中HUD开发的资源包,包含示例代码和可能的教程材料。 描述中提到的"OSG中hud的使用方法与示例代码",意味着这个压缩包可能包含了如何在OSG应用程序中...

    Zemax设计的HUD案例光路

    Zemax软件设计的HUD光路,抬头显示系统(Head Up Display,HUD)也称为平视显示系统。HUD技术是20世纪60 年代在光学瞄准和雷达瞄准基础上发展起来的,最早应用在战斗机上,HUD可以将重要的信息,如速度、油量、转速...

    ios hud提示框

    在iOS应用开发中,HUD(Head Up Display)提示框是一种常用的用户界面元素,它能够向用户提供操作反馈,显示加载状态或者简单的信息提示。"ios hud 提示框"这个主题主要涵盖了如何在iOS应用中实现和使用这类提示框,...

    汽车HUD光学系统.pptx

    汽车HUD光学系统 本资源摘要信息主要介绍了汽车HUD(Head-Up Display)光学系统的知识点。HUD是一种飞行辅助仪器,最初应用于航空器上,后来逐渐应用于汽车行业。 HUD系统可以将重要信息投射到驾驶员的视野前方,不...

    基于osg 相机实现hud菜单

    基于osg Camera 实现hud菜单。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

    hud3001源代码

    hud3001源代码

    HUD开发资料含代码.rar

    《HUD技术深度解析:从设计到实践》 抬头看向前方,汽车挡风玻璃上清晰地显示着速度、导航指示、交通标志识别等信息,这就是抬头显示(Head-Up Display,简称HUD)技术的魅力所在。江森自控作为全球知名的汽车零...

    座舱智能化引发交互革命,ARHUD乘风而来(2021)(33页).pdf

    座舱智能化引发交互革命,ARHUD乘风而来 本文对座舱智能化的发展趋势和AR-HUD技术的应用进行了深入分析,预计2025年国内HUD市场空间可达到290亿,2020-2025年行业复合增长率高达92.1%。同时,本文也对AR-HUD技术的...

    微信小程序HUD

    微信小程序HUD是一款基于微信小程序平台开发的用户界面头部显示组件,通常用于在应用程序中提供反馈信息,如加载状态、提示信息等。它采用JavaScript进行编写,利用了微信小程序的开发框架,为开发者提供了便捷的...

    汽车抬头显示(HUD)突破驾驶员传统视角

    在这一系列创新技术中,汽车抬头显示(HUD)技术的出现,为驾驶员提供了一种全新的视角和交互方式,颠覆了传统的驾驶模式。 HUD技术的核心在于它能够将驾驶信息以图形或文字的形式直接投射到驾驶员前方的挡风玻璃上...

    ios-自定义HUD.zip

    `HUD`(Head Up Display)是一种在屏幕上短暂显示信息,以指示应用正在进行后台处理或加载数据的状态。本教程将重点讲解如何在iOS应用中自定义绘制文字动画和加载动画,创建一个符合应用风格的指示器。 首先,我们...

    HUD Navigation System 2.0.3.rar

    《Unity中的HUD Navigation System 2.0.3:构建高效导航界面的新里程》 在现代游戏开发中,用户界面(UI)的设计与功能是至关重要的,尤其是Head-Up Display(HUD)导航系统,它能为玩家提供实时的游戏信息,增强...

    ugui hud 加了跟随隐藏代码

    hud unity3d ugui

    [资源插件]Unity3D_UGUI HUD Text v1.4.1.zip

    HudText(Head-Up Display Text)是一种特定类型的UI元素,通常用于在游戏中显示即时信息,如玩家的生命值、分数、提示信息或者像“飘血效果”、“飘伤害效果”和“飘数字效果”这样的动态视觉效果。这些效果能增强...

    LG HUD相关专利曝光 欲打造汽车专用柔性透明显示屏

    该公司不断在柔性显示屏技术领域取得突破,最近又曝光了一项新的HUD(Head-Up Display,平视显示器)技术专利。这项专利显示LG将目光投向了汽车领域,并致力于打造专为汽车设计的柔性透明显示屏。 首先,我们需要...

    ios-非常灵活的HUD.zip

    一款支持支持自定义的轻量级HUD,支持垂直、水平两种样式。SVProgressHUD非常灵活,所见的部分都可根据自己的要求进行自定义,包括自义动画效果或图片,只需要实现相关协议方法。 安装使用 pod 'XNProgressHUD' ...

    HUD_Text_v1.11.unitypackage

    NGUI: HUD Text Copyright 漏 2012-2014 Tasharen Entertainment Version 1.11 http://www.tasharen.com/forum/index.php?topic=997.0 -------------------------------------------------- Thank you for ...

    ios-一个简单的hud提示框.zip

    在iOS应用开发中,用户界面的交互体验是至关重要的,其中一种常见的设计元素就是提示框(HUD,Head-Up Display)。HUD通常用于显示短暂的通知、加载进度或者操作反馈,以提高用户体验。本项目“ios-一个简单的hud...

Global site tag (gtag.js) - Google Analytics