HDU1175 连连看(BFS)

HDU1175 连连看(BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1175

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

分析:首先要注意题目中的限制条件要是相同的格子,且只能走空格,转弯次数不能超过2次.

所以状态设计为:

struct Node

{

int r,c,

int dir;//当前朝向

int step;//step表示转弯次数

};

因为转弯次数有限制,所以如果我们之前走到(2,2)点朝上方向转了2次弯,但是现在我们走到(2,2)点朝上方向转了3次弯,我们应该放弃该状态,因为(2,2,0,3)能到达的后继节点(2,2,0,2)肯定能到.且如果我们到(2,2)(朝上方向)现在只转了1次弯,那么我们应该用1去跟新dist[2][2][dir].(dist数组表示在(r,c)点且当前方向为dir时的最小转弯的次数).

剩下的就是基本的BFS过程了.

我看网上dist[r][c]只有二维,没有方向这一维度.然后他们用转弯次数小的值去更新dist,这样做也是行的.虽然忽略了方向,但是要注意如果当前状态的转弯次数<=dist[r][c],那么就是合法的,需要扩展其后继,而不是当前状态的转弯次数<dist[r][c]时才扩展.

因为此时新的状态可能和你记录的dist的方向不一致,如果因为转弯次数相等就放弃该点,就可能失去正解.你以前记录的那个dist可能是朝上的,朝上可能不能到终点,人家这个新状态虽然转弯次数和你的一样,但是是朝右的,朝右可以直接到终点.那么如果你放弃新状态,就出错.

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1000+10;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
int R,C;
int sr,sc,er,ec;
int map[maxn][maxn];
int dist[maxn][maxn][4];
struct Node
{
    int r,c;
    int dir;//当前朝向
    int step;//step表示转弯次数
    Node(int r,int c,int dir,int s):r(r),c(c),dir(dir),step(s){}
};
bool BFS()
{
    queue<Node> Q;
    for(int d=0;d<4;d++) Q.push(Node(sr,sc,d,0)),dist[sr][sc][d]=0;
    memset(dist,-1,sizeof(dist));

    while(!Q.empty())
    {
        Node node=Q.front(); Q.pop();
        int r=node.r, c=node.c, dir=node.dir, step=node.step;
        for(int d=0;d<4;d++)
        {
            int nr=r+dr[d], nc=c+dc[d], nstep= (dir==d)?step:step+1;
            if(nr<=0||nr>R||nc<=0||nc>C||nstep>2) continue;//非法
            if(nr==er && nc==ec) return true;              //终点
            if(map[nr][nc]!=0) continue;                   //非空格且不是终点,所以不能走
            if(dist[nr][nc][d]==-1 || dist[nr][nc][d] > nstep)
            {
                dist[nr][nc][d]=nstep;
                Q.push(Node(nr,nc,d,nstep));
            }
        }
    }
    return false;
}
int main()
{
    while(scanf("%d%d",&R,&C)==2&&R&&C)
    {
        for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            scanf("%d",&map[i][j]);
        int q; scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d%d",&sr,&sc,&er,&ec);
            if(map[sr][sc]==0||map[er][ec]==0||map[sr][sc]!=map[er][ec])
                printf("NO\n");
            else if(sr==er && sc==ec) printf("YES\n");
            else printf("%s\n",BFS()?"YES":"NO");
        }
    }
    return 0;
}