您的位置: 首页  >  IT文章  >  hdu1175 连连看（bfs+dfs） 连连看

hdu1175 连连看（bfs+dfs） 连连看

分类: IT文章 • 2022-07-16 09:40:17
Time Limit : 20000/10000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 4   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

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 <string.h>
using namespace std;;
int map[1005][1005];
int visit[1005][1005];
int n,m,x1,y3,x2,y2,ans;
int dir[4][2]= {-1,0,1,0,0,-1,0,1}; //上下左右
void dfs(int x,int y,int mark,int count)//x,y坐标，z朝向(1:up,2:down,3:left,4right)，k转弯次数
{
    int i,xx,yy;
    if(count>3) return;
    if(x==x2&&y==y2)
    {
        ans=1;
        return;
    }
    visit[x][y]=1;
    if(map[x][y]!=0&&count!=0) return;
    for(i=0; i<4&&!ans; i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(xx<1||xx>n||yy<1||yy>m) continue;
        if(visit[xx][yy]==1)continue;
        if(mark==i)
            dfs(xx,yy,mark,count);
        else if(mark!=i)
            dfs(xx,yy,i,count+1);//i表示当前方向，p表示上一步的方向，t表示转折次数
        visit[xx][yy]=0;
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
            break;
        int i,j;
        for(i = 1; i<=n; i++)
        {
            for(j = 1; j<=m; j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
            memset(visit,0,sizeof(visit));
            scanf("%d%d%d%d",&x1,&y3,&x2,&y2);
            ans=0;

            if((x1 ==x2 &&y3 ==y2 )||(map[x1][y3]==0&&map[x2][y2]==0)||map[x1][y3]!=map[x2][y2])
            {
                printf("NO
");
            }
            else
            {
                dfs(x1,y3,-1,0);
                if(ans)
                    printf("YES
");
                else
                    printf("NO
");
            }


        }
    }

    return 0;
}

广搜：注意判断条件

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,ax,ay,bx,by;
int ans;
int map[1005][1005];
int visit[1005][1005];
int dir[4][2]= {-1,0,1,0,0,-1,0,1};
struct nodes
{
    int x,y,d,t;
};
nodes node1,node2;
void bfs()
{
    queue<nodes> q;
    while(!q.empty())
    q.pop();
    node1.x=ax;
    node1.y=ay;
    node1.d=-1;
    node1.t=0;
    //visit[ax][ay]=1;
    q.push(node1);
    while(!q.empty())
    {
        node1=q.front();
        q.pop();

        if(node1.x==bx&&node1.y==by&&node1.t<=2)
        {
            ans=1;
            return;
        }
        for(int i=0;i<4;i++)
        {
            node2.x=node1.x+dir[i][0];
            node2.y=node1.y+dir[i][1];
            if(node1.d==-1)
                {
                    node2.d=i;
                    node2.t=0;
                }
                else if(node1.d!=i)
                {
                    node2.d=i;
                    node2.t=node1.t+1;
                }
                else
                {
                    node2.d=i;
                    node2.t=node1.t;
                }
             //  if(node2.x>0&&node2.x<=n&&node2.y>0&&node2.y<=m&&node2.t<=2&&!visit[node2.x][node2.y]&&(!map[node2.x][node2.y]||(node2.x==bx&&node2.y==by)))

            if(node2.x>0&&node2.x<=n&&node2.y>0&&node2.y<=m&&node2.t<=2&&(node2.t<=visit[node2.x][node2.y])&&(!map[node2.x][node2.y]||(node2.x==bx&&node2.y==by)))
            {
                //visit[node2.x][node2.y]=1;//单纯的标记会wa
                visit[node2.x][node2.y]=node2.t;

                q.push(node2);
            }
        }
    }
    return ;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
            break;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
            ans=0;
            // memset(visit,0,sizeof(visit));
            memset(visit,1,sizeof(visit));
            scanf("%d%d%d%d",&ax,&ay,&bx,&by);
            if(!(ax==bx&&ay==by)&&map[ax][ay]!=0&&map[bx][by]!=0&&map[ax][ay]==map[bx][by])
            {
                bfs();
            }
            if(ans)
            printf("YES
");
            else
            printf("NO
");
        }
    }
}

相关推荐