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 41 2 3 40 0 0 04 3 2 141 1 3 41 1 2 41 1 3 32 1 2 43 40 1 4 30 2 4 10 0 0 021 1 2 41 3 2 30 0Sample Output
YESNONONONOYES
如同正常的BFS一样，只是每次拓展路径要拓展一条直线，记录下到该点转过的拐角，拓展3层(两个拐角)
判断目标点是否能到达即可
1 /* 2 By:OhYee 3 Github:OhYee 4 Email:oyohyee@oyohyee.com 5 Blog:http://www.cnblogs.com/ohyee/ 6 7 かしこいかわいい？ 8 エリーチカ！ 9 要写出来Хорошо的代码哦~ 10 */ 11 12 #include <cstdio> 13 #include <algorithm> 14 #include <cstring> 15 #include <cmath> 16 #include <string> 17 #include <iostream> 18 #include <vector> 19 #include <list> 20 #include <queue> 21 #include <stack> 22 using namespace std; 23 24 //DEBUG MODE 25 #define debug 0 26 27 //循环 28 #define REP(n) for(int o=0;o<n;o++) 29 30 const int maxn = 1005; 31 32 int m,n; 33 int Map[maxn][maxn]; 34 int dis[maxn][maxn]; 35 36 typedef pair<int,int> point; 37 38 int BFS(int s1,int s2,int v1,int v2) { 39 #define con1(nn) (nn<=0||nn>n) 40 #define con2(mm) (mm<=0||mm>m) 41 //位置错误 42 if(con1(s1) || con1(v1) || con2(s2) || con2(v2)) 43 return -1; 44 //同一位置 45 if(s1 == v1 && s2 == v2) 46 return -1; 47 //棋子不同 或 无棋子 48 if(Map[s1][s2] != Map[v1][v2] || Map[s1][s2]==0) 49 return -1; 50 51 queue<point> Q; 52 memset(dis,-1,sizeof(dis)); 53 54 Q.push(point(s1,s2)); 55 dis[s1][s2] = 0; 56 57 while(!Q.empty()) { 58 int th1 = Q.front().first; 59 int th2 = Q.front().second; 60 Q.pop(); 61 62 //达到终点 63 if(th1 == v1 && th2 == v2) 64 break; 65 66 //拓展节点 67 #define condition 68 (next1 > 0 && next1 <= n && next2 > 0 && next2 <= m 69 && (Map[next1][next2] == 0||(next1==v1 && next2==v2))) 70 71 #define push 72 if(dis[next1][next2]==-1 && dis[th1][th2]<=2) { 73 Q.push(point(next1,next2)); 74 dis[next1][next2] = dis[th1][th2] + 1; 75 } 76 77 int next1,next2; 78 for(next1 = th1,next2 = th2 + 1;condition;next2++) { 79 push; 80 } 81 for(next1 = th1 + 1,next2 = th2;condition;next1++) { 82 push; 83 } 84 for(next1 = th1,next2 = th2 - 1;condition;next2--) { 85 push; 86 } 87 for(next1 = th1 - 1,next2 = th2;condition;next1--) { 88 push; 89 } 90 91 } 92 return dis[v1][v2]; 93 } 94 95 bool Do() { 96 if(scanf("%d%d",&n,&m),n == 0 && m == 0) 97 return false; 98 for(int i = 1;i <= n;i++) 99 for(int j = 1;j <= m;j++) 100 scanf("%d",&Map[i][j]); 101 int T; 102 scanf("%d",&T); 103 while(T--) { 104 int s1,s2,v1,v2; 105 scanf("%d%d%d%d",&s1,&s2,&v1,&v2); 106 printf("%s\n",BFS(s1,s2,v1,v2)==-1?"NO":"YES"); 107 } 108 return true; 109 } 110 111 int main() { 112 while(Do()); 113 return 0; 114 }
原文：http://www.cnblogs.com/ohyee/p/5399960.html