Time Limit: 10000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
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
思路:搜,我用的是BFS。要记录转弯的次数,但出发不算进去。一个点是可以多次进过的,所以不能简单标记。去重标记应该是经过点的坐标和经过的方向,只能从每个方向经过一次。还有搜之前就能判断的情况:自己不能消除自己(即起点和终点不能相同),起点和终点不能是空位,起点和终点的值要相同。
AC代码:
#include <cstdio> #include <queue> #include <cstring> using namespace std; int map[1010][1010]; bool vis[1010][1010][5]; const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; int m, n; struct node { int x, y, turn, dir; bool operator == (const node b) { return x == b.x && y == b.y; } }; node start, goal; queue <node> q; void input() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]); } bool check(int x, int y) { if (x < 1 || x > n || y < 1 || y > m) return 0; return 1; } void pre() { while (!q.empty()) q.pop(); memset(vis, 0, sizeof(vis)); } void bfs() { pre(); start.turn = 0; start.dir = -1; q.push(start); while (!q.empty()) { node u = q.front(); q.pop(); if (u.turn > 2) continue; if (u == goal) { printf("YES\n"); return; } node next; for (int i = 0; i < 4; i++) { next.x = u.x + dx[i]; next.y = u.y + dy[i]; if (!check(next.x, next.y) || vis[next.x][next.y][i]) continue; if (map[next.x][next.y] && !(next == goal)) continue; vis[u.x][u.y][i] = 1; next.turn = u.turn; next.dir = i; if (u.dir != -1 && u.dir != i) next.turn++; q.push(next); } } printf("NO\n"); } void solve() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d%d", &start.x, &start.y, &goal.x, &goal.y); if (!map[start.x][start.y] || map[start.x][start.y] != map[goal.x][goal.y] || start == goal) { printf("NO\n"); continue; } bfs(); } } int main() { while (scanf("%d%d", &n, &m) == 2 && m && n) { input(); solve(); } return 0; }
0 条评论