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 }