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

????YES
????NO
????NO
????NO
????NO
????YES

思路：

? ? 一條路徑最多只能轉(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)查找。

Source Program

#include<queue> #include<cstdio> #include<iostream> #include<cstring> using namespace std;int n,m; int map[1001][1001]; int v[1001][1001]; int x1,y1,x2,y2; bool flag; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向數(shù)組 struct node {int x;int y;int trun; }start,endd;queue<node> q;bool judge(int x0,int y0) {if(x0<0||x0>=n||y0<0||y0>=m)return true;if(x0==x2-1&&y0==y2-1)return false;if(map[x0][y0]!=0)return true;return false; }void bfs(int x0,int y0) {int i;while(!q.empty())//隊(duì)列清零q.pop();start.x=x0;start.y=y0;start.trun=-1;v[x0][y0]=1;q.push(start);//元素入列while(!q.empty()){start=q.front();q.pop();//元素出列if(start.trun>=2) continue;for(i=0;i<4;i++){endd.x=start.x+dir[i][0];endd.y=start.y+dir[i][1];endd.trun=start.trun+1;if(judge(endd.x,endd.y)) continue;//越界判斷while(judge(endd.x,endd.y)==0){if(endd.x==x2-1&&endd.y==y2-1){flag=true;return;}if(v[endd.x][endd.y]==0){q.push(endd);//元素入列v[endd.x][endd.y]=1;}endd.x+=dir[i][0];endd.y+=dir[i][1];}}} }int main() {int t;int i,j;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&map[i][j]);scanf("%d",&t);for(i=0;i<t;i++){flag=false;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);if(x1==x2&&y1==y2)//起點(diǎn)終點(diǎn)相同，不行{printf("NO\n");continue;}if(map[x1-1][y1-1]!=map[x2-1][y2-1]||map[x1-1][y1-1]==0||map[x2-1][y2-1]==0)//起點(diǎn)或者終點(diǎn)為0，起點(diǎn)終點(diǎn)不同，不行{printf("NO\n");continue;}memset(v,0,sizeof(v));bfs(x1-1,y1-1);if(flag)printf("YES\n");elseprintf("NO\n");}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的连连看（HDU-1175）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。