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
一看题目就知道是用bfs，但是要注意几个问题：bfs是按层次进行搜索，得到的从起点到终点的路径(如果存在的话)是最短的。题目中说这条路径最多只能转向2次，有一些情况可能得到了从起点到终点的路径，但是它的转向次数已经超过的2次，这样这条路径就不符合要求，得重新找一条。一个一般的结论：如果某一点记录的转向次数大于当前路径在该点的转向次数，那么还能从该点再发出一条路径来查找。可以用一个二维数组hash[n][n]来状态判重，这个数组里存的数值就是某条路径在该点的转向次数，if(hash[x][y]>=now.turn) q.push(now)；还有个需要注意的就是能连上的点并没有从图中消失，所以每条查询语句都是独立的。(我把它当成真正的连连看来做，结果WA了10次)
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 const int N = 1001;
6 bool flag;
7 int n,m,sx,sy,ex,ey;
8 int hash[N][N],map[N][N];
9 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
10 struct node{
11 int x,y,turn,d;
12 }start;
13 queue<node> q;
14
15 inline bool in(const node &p){
16 if(p.x<0 || p.y<0 || p.x>=n || p.y>=m)
17 return false;
18 return true;
19 }
20 void bfs(){
21 node now,t;
22 while(!q.empty()){
23 now=q.front(),q.pop();
24 if(now.x==ex && now.y==ey && now.turn<=2){
25 flag=true;
26 return;
27 }
28 for(int i=0;i<4;i++){
29 t.x=now.x+dir[i][0],t.y=now.y+dir[i][1];
30 if(now.d==i)
31 t.turn=now.turn,t.d=now.d;
32 else
33 t.turn=now.turn+1,t.d=i;
34 if(in(t) && (map[t.x][t.y]==0||t.x==ex&&t.y==ey) && hash[t.x][t.y]>=t.turn)
35 hash[t.x][t.y]=t.turn,q.push(t);
36 }
37 }
38 }
39 int main(){
40 int i,j,t;
41 while(scanf("%d %d",&n,&m),n||m){
42 for(i=0;i<n;i++)
43 for(j=0;j<m;j++) scanf("%d",&map[i][j]);
44 scanf("%d",&t);
45 while(t--){
46 scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
47 sx--,sy--,ex--,ey--;
48 if((map[sx][sy]!=map[ex][ey]) || map[sx][sy]==0 || map[ex][ey]==0 || (sx==ex&&sy==ey)){
49 puts("NO");
50 continue;
51 }
52 for(i=0;i<n;i++)
53 for(j=0;j<m;j++) hash[i][j]=11;
54 while(!q.empty()) q.pop();
55 for(i=0;i<4;i++){
56 start.x=sx,start.y=sy,start.turn=0,start.d=i;
57 q.push(start);
58 }
59 flag=false,hash[sx][sy]=0;
60 bfs();
61 puts(flag ? "YES":"NO");
62 }
63 }
64 return 0;
65 }