class="markdown_views prism-tomorrow-night"> 《连连看》是由一款益智类游戏。
《连连看》只要将相同的两张牌用三根以内的直线连在一起就可以消除，规则简单容易上手。
本题编写程序模拟人进行连连看游戏，电脑模拟人玩连连看的过程如下：
1、分析本局游戏，将本局游戏转化成一个二位数组。0表示空白区域，数字表示该游戏牌为出现在游戏中的第几类游戏牌。
2、利用广度优先搜索算法，判断两个游戏牌是否可以消除。
3、程序模拟人点击可以消除的一对游戏牌进行消除。
对某局游戏转化成二维数组如下：
0 0 0 0 0
0 1 2 0 0
0 0 3 4 0
0 0 0 1 0
输入二位数组的行、列，二位数组、起始元素的的坐标、终止元素的坐标，判断起始游戏牌和终止游戏牌是否可以消除。
对上例输入
4 5
0 0 0 0 0 0 1 2 0 0 0 0 3 4 0 0 0 0 1 0
1 1
3 3
输出 TRUE 测试用例
用例1：
输入：
4 5
0 0 0 0 0 0 1 2 0 0 0 0 3 4 0 0 0 0 1 0
1 1
3 3
输出：TRUE
用例2：
输入：
5 6
0 0 0 0 0 0 0 1 2 3 0 0 3 0 0 0 0 3 0 2 3 4 0 2 0 0 0 2 1 4
1 1
4 4
输出：TRUE
用例3：
输入：
5 6
0 0 0 0 0 0 0 1 2 3 0 0 3 0 0 0 0 3 0 2 3 4 0 2 0 0 0 2 1 4
3 3
4 5
输出：FALSE 解析：注意入队条件有只能在图的边界内连线（只能在图内，不是我们平常玩的那种可以越边的）、转向次数不能超过3、除终点外的非0数字是障碍、要么没遍历过要么遍历过但这次转向次数要少。

代码

#include #include using namespace std; int Map[1000][1000] = { 0 }; int vir[1000][1000] = { 0 }; int m, n, stx, sty, edx, edy; int trend[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//0-下，1-上，2-右，3-左 struct node { int x, y;//坐标 int dir; //方向 int turn;//转弯次数 }; void BFS() { queueq; node k0,k1, t0; int flag = 0; for (int i = 0; i < 4; i++) { t0.x = stx + trend[i][0]; t0.y = sty + trend[i][1]; t0.dir = i; t0.turn = 1; vir[t0.x][t0.y] = t0.turn; q.push(t0); } while (!q.empty()) { k0 = q.front(); q.pop(); if (k0.x==edx&&k0.y==edy) { flag = 1; cout << "TRUE" << endl; break; } for (int i = 0; i < 4; i++) { k1.x = k0.x + trend[i][0]; k1.y = k0.y + trend[i][1]; k1.dir = i; if (k1.dir != k0.dir) k1.turn = k0.turn + 1; else k1.turn = k0.turn; if (k1.turn > 3 || k1.x<0 || k1.y<0 || k1.x>m - 1 || k1.y>n - 1) continue; if (Map[k1.x][k1.y] != 0 && Map[k1.x][k1.y] != Map[edx][edy]) continue; if (vir[k1.x][k1.y] == 0 || vir[k1.x][k1.y] >= k1.turn) { vir[k1.x][k1.y] = k1.turn; q.push(k1); } } } if (!flag) cout << "FALSE" << endl; } int main() { cin >> m >> n; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> Map[i][j]; cin >> stx >> sty >> edx >> edy; BFS(); return 0; }