hdoj 1175 连连看【bfs】

心已赠人 2022-08-08 14:42 116阅读 0赞

# 连连看 #

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

解析：题目中说只有相同的格子才能相消，所以，在输入两个点后，可以先判断两个棋子是否一样，不相同直接poss；还要考虑两个坐标相同的情况。

设计结构体时要包含四要素，即横坐标、纵坐标、方向、到达当前点拐弯的总次数。

Accept代码【c++】

#include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    struct Node {
    	int a, b, c, d;
    	Node(){}
    	Node(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}
    };
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int n, m;
    int map[1001][1001];
    bool vis[1001][1001];
    
    void BFS(int x1, int y1, int x2, int y2) {
    	queue <Node> Q;
    	memset(vis, 0, sizeof(vis));
    	Q.push(Node(x1, y1, 4, 0));			//起点入队 
    	while(!Q.empty()) {
    		Node fang;
    		fang.a = Q.front().a, fang.b = Q.front().b, fang.c = Q.front().c, fang.d = Q.front().d;
    		Q.pop();
    		vis[fang.a][fang.b] = true;
    		for(int i = 0; i < 4; i++) {
    			int x = fang.a + dx[i];
    			int y = fang.b + dy[i];
    			int total = fang.d;			//到达当前棋子，总共转弯的次数 
    			if(fang.c != 4 && fang.c != i)		//是否转弯 
    				total++;
    			if(x <= 0 || x > n || y <= 0 || y > m || vis[x][y] || total > 2)	//是否出界 
    				continue;
    			if(x == x2 && y ==y2) {
    				printf("YES\n");
    				return;
    			}
    			if(map[x][y] != 0)
    				continue;
    			Q.push(Node(x, y, i, total));			//当前点入队
    		}
    	}
    	printf("NO\n");
    }
    
    int main() {
    	while(scanf("%d%d", &n, &m), n, m){
    		memset(map, -1, sizeof(map));
    		for(int i = 1; i <= n; i++)
    			for(int j = 1; j <= m; j++)
    				scanf("%d", &map[i][j]);
    		int x1, y1, x2, y2, q = 0;
    		scanf("%d", &q);
    		while(q--) {
    			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    			if(map[x1][y1] == 0 || map[x2][y2] == 0 || map[x1][y1] != map[x2][y2])
    				printf("NO\n");
    			else if(x1 == x2 && y1 == y2)
    				printf("YES\n");
    			else
    				BFS(x1, y1, x2, y2);
    		}
    	}
    	return 0;
    }