Problem Description
“連連看”相信很多人都玩過(guò)。沒(méi)玩過(guò)也沒(méi)關(guān)系，下面我給大家介紹一下游戲規(guī)則：在一個(gè)棋盤中，放了很多的棋子。如果某兩個(gè)相同的棋子，可以通過(guò)一條線連起來(lái)（這條線不能經(jīng)過(guò)其它棋子），而且線的轉(zhuǎn)折次數(shù)不超過(guò)兩次，那么這兩個(gè)棋子就可以在棋盤上消去。不好意思，由于我以前沒(méi)有玩過(guò)連連看，咨詢了同學(xué)的意見(jiàn)，連線不能從外面繞過(guò)去的，但事實(shí)上這是錯(cuò)的。現(xiàn)在已經(jīng)釀成大禍，就只能將錯(cuò)就錯(cuò)了，連線不能從外圍繞過(guò)。
玩家鼠標(biāo)先后點(diǎn)擊兩塊棋子，試圖將他們消去，然后游戲的后臺(tái)判斷這兩個(gè)方格能不能消去。現(xiàn)在你的任務(wù)就是寫這個(gè)后臺(tái)程序。
Input
輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行有兩個(gè)正整數(shù)n,m(0<n<=1000,0<m<1000)，分別表示棋盤的行數(shù)與列數(shù)。在接下來(lái)的n行中，每行有m個(gè)非負(fù)整數(shù)描述棋盤的方格分布。0表示這個(gè)位置沒(méi)有棋子，正整數(shù)表示棋子的類型。接下來(lái)的一行是一個(gè)正整數(shù)q(0<q<50)，表示下面有q次詢問(wèn)。在接下來(lái)的q行里，每行有四個(gè)正整數(shù)x1,y1,x2,y2,表示詢問(wèn)第x1行y1列的棋子與第x2行y2列的棋子能不能消去。n=0,m=0時(shí)，輸入結(jié)束。
注意：詢問(wèn)之間無(wú)先后關(guān)系，都是針對(duì)當(dāng)前狀態(tài)的！
Output
每一組輸入數(shù)據(jù)對(duì)應(yīng)一行輸出。如果能消去則輸出"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，但是要注意幾個(gè)問(wèn)題：bfs是按層次進(jìn)行搜索，得到的從起點(diǎn)到終點(diǎn)的路徑(如果存在的話)是最短的。題目中說(shuō)這條路徑最多只能轉(zhuǎn)向2次，有一些情況可能得到了從起點(diǎn)到終點(diǎn)的路徑，但是它的轉(zhuǎn)向次數(shù)已經(jīng)超過(guò)的2次，這樣這條路徑就不符合要求，得重新找一條。一個(gè)一般的結(jié)論：如果某一點(diǎn)記錄的轉(zhuǎn)向次數(shù)大于當(dāng)前路徑在該點(diǎn)的轉(zhuǎn)向次數(shù)，那么還能從該點(diǎn)再發(fā)出一條路徑來(lái)查找。可以用一個(gè)二維數(shù)組hash[n][n]來(lái)狀態(tài)判重，這個(gè)數(shù)組里存的數(shù)值就是某條路徑在該點(diǎn)的轉(zhuǎn)向次數(shù)，if(hash[x][y]>=now.turn) q.push(now)；還有個(gè)需要注意的就是能連上的點(diǎn)并沒(méi)有從圖中消失，所以每條查詢語(yǔ)句都是獨(dú)立的。(我把它當(dāng)成真正的連連看來(lái)做，結(jié)果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 }