【HDU】1175 连连看（BFS + 剪枝）
目录
1.题目描述
2.输入输出
3.解题思路
4.样例解析
5.代码实现
1.题目描述
“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。输入数据有多组。每组数据的第一行有两个正整数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时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！
2.输入输出
输入样例:
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
输出样例:
YES
NO
NO
NO
NO
YES
3.解题思路
这道题不同于寻常的 BFS 问题，他的限制条件在于 “转向”
本质上来说，题目所求解的是从 x1,y1 到 x2,y2 是否存在一条合法路径
之前所遇到的 标记数组 通常情况下是经过了这个点后将其标记，以后不再从这点经过
但在这题里面这个标记数组记录的应该是 转弯次数 的最小值
如果在 （i, j）这一点目前的转弯次数 step <= turn[i][j] , 那么就 Push 到队列里
因为从起点到一个点的路径有很多条，如果这点已经经过了就不再考虑的话，可能会忽略掉从这个点经过的其他转弯次数更好的路径（有点贪心的味道）
所以我们 标记数组 只存 小于或者是等于目前最小的 转弯次数 的路线
另外一种思路，参考了大佬的文章：
BFS——1175连连看_timer_catch的博客-CSDN博客
我们可以这样来拓展：一次性将一条直线上可以拓展的点全部拓展
每次都往四个方向进行直线拓展，同时也相当于是总步数 == 2时的剪枝操作
4.样例解析
5.代码实现
方法一
首先是方向的判断：
使用 0 1 2 3 来表示 四个方向， 同时也是与下面的 dx[], dy[] 数组所表示的方向数组相对应
然后是每个结点的组成 （坐标 + 方向 + 目前的转向次数）
struct Node{ int x, y; int dir; int step;};
正常的读入 操作
核心代码 ： BFS 函数
首先是进行最开始的判断
① 所连接的两个元素是否相等
② 所连接的两个元素是否都是 0
接下来创建 BFS 中常用的队列， 初始化起点的结点
当队列里面还有元素的时候，将队头元素取出，先判断其是不是终点
然后是往队头元素周围的四个方向进行拓展，存在以下限制条件：
①需要在地图的范围内
②下一个拓展的点必须是空格（0） 或者 是终点
当我们可以拓展点的时候，需要进行以下判断：
因为我们初始化起点的方向为-1，所以下一个点可以往任意方向拓展
当入队的点不是起点的时候，需要判断它和队头元素方向是否一致
最后再与记录地图上每个点的转向次数最小值的 turn[i][j] 进行比较，如果小于等于，则可以入队
方法二
创建一个结构体，记录坐标和当前的总步数
同样初始的判断操作
在这种方法中，每个点只会被遍历一遍，所以我们需要用一个st数组来记录当前这个点是否走过，因此还有一步 额外的初始化操作
然后将起点加入队头
如果当前这个点已经到达终点，则返回正确
如果当前这个点不是终点且总步数为2，那么它已经不可能再向其他方向拓展，直接跳过
利用check函数，一次性将一条线上能满足条件的点全部放入队列中
同时利用了初始化起点的步数为-1的操作
AC代码
方法一：
#include #include #include #define PII pair using namespace std;const int N = 1010;int n, m, T;int a1, b1, a2, b2;int g[N][N]; //记录地图int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};//记录每个点的方向//0 1 2 3 //上 下 左 右int turn[N][N]; //记录转向的次数struct Node{ int x, y; int dir; int step;};bool bfs(){ //两个元素不相等 if(g[a1][b1] != g[a2][b2]) return false; if(g[a1][b1] == 0 && g[a2][b2] == 0) return false; memset(turn, 20, sizeof turn); queue q; q.push({a1, b1, -1, 0}); turn[a1][b1] = 0; Node temp, s; s.x = a1, s.y = b1, s.dir = -1, s.step = 0; while(q.size()) { temp = q.front(); q.pop(); if(temp.x == a2 && temp.y == b2 && temp.step <= 2) return true; for(int i = 0; i = 1 && s.x = 1 && s.y <= m && (g[s.x][s.y] == 0 || (s.x == a2 && s.y == b2))) { if(s.dir != -1) { if(i != s.dir) { s.dir = i; s.step ++ ; } } else s.dir = i; if(s.step <= turn[s.x][s.y]) { turn[s.x][s.y] = s.step; q.push(s); } } } } return false;}int main(){ while(scanf("%d %d", &n, &m) && (n != 0 && m != 0)) { for(int i = 1; i <= n; i ++ ) for(int j = 1; j > g[i][j]; cin >> T; while(T -- ) { cin >> a1 >> b1 >> a2 >> b2; if(bfs()) puts("YES"); else puts("NO"); } } return 0;}
方法二：
#include #include #include #define PII pair using namespace std;const int N = 1010;int n, m, T;int a1, b1, a2, b2;int g[N][N]; //记录地图bool st[N][N];int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};struct Node{ int x, y; int step;};bool check(int x, int y){ if(x == a2 && y == b2) return true; if(x n || y m || g[x][y] || st[x][y]) return false; return true;}bool bfs(){ //两个元素不相等 if(g[a1][b1] != g[a2][b2]) return false; if(g[a1][b1] == 0 || g[a2][b2] == 0) return false; memset(st, false, sizeof st); queue q; q.push({a1, b1, -1}); st[a1][b1] = true; while(q.size()) { auto temp = q.front(); q.pop(); if(temp.x == a2 && temp.y == b2) return true; if(temp.step == 2) continue; for(int i = 0; i < 4; i ++ ) { int a = temp.x + dx[i], b = temp.y + dy[i]; while(check(a, b)) { q.push({a, b, temp.step + 1}); st[a][b] = true; a += dx[i], b += dy[i]; } } } return false;}int main(){ while(scanf("%d %d", &n, &m) && (n != 0 && m != 0)) { for(int i = 1; i <= n; i ++ ) for(int j = 1; j > g[i][j]; cin >> T; while(T -- ) { cin >> a1 >> b1 >> a2 >> b2; if(bfs()) puts("YES"); else puts("NO"); } } return 0;}