Problem Description “連連看”相信很多人都玩過。沒玩過也沒關(guān)系，下面我給大家介紹一下游戲規(guī)則：在一個棋盤中，放了很多的棋子。如果某兩個相同的棋子，可以通過一條線連起來（這條線不能經(jīng)過其它棋子），而且線的轉(zhuǎn)折次數(shù)不超過兩次，那么這兩個棋子就可以在棋盤上消去。不好意思，由于我以前沒有玩過連連看，咨詢了同學(xué)的意見，連線不能從外面繞過去的，但事實上這是錯的。現(xiàn)在已經(jīng)釀成大禍，就只能將錯就錯了，連線不能從外圍繞過。
玩家鼠標(biāo)先后點擊兩塊棋子，試圖將他們消去，然后游戲的后臺判斷這兩個方格能不能消去。現(xiàn)在你的任務(wù)就是寫這個后臺程序。

Input 輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行有兩個正整數(shù)n,m(0<n<=1000,0<m<1000)，分別表示棋盤的行數(shù)與列數(shù)。在接下來的n行中，每行有m個非負(fù)整數(shù)描述棋盤的方格分布。0表示這個位置沒有棋子，正整數(shù)表示棋子的類型。接下來的一行是一個正整數(shù)q(0<q<50)，表示下面有q次詢問。在接下來的q行里，每行有四個正整數(shù)x1,y1,x2,y2,表示詢問第x1行y1列的棋子與第x2行y2列的棋子能不能消去。n=0,m=0時，輸入結(jié)束。
注意：詢問之間無先后關(guān)系，都是針對當(dāng)前狀態(tài)的！

Output 每一組輸入數(shù)據(jù)對應(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
題目鏈接?
代碼注釋很纖細，看代碼：
#include<iostream> #include<cstdio> #include<queue> #include <limits.h> using namespace std;struct node{int x,y; //x為行標(biāo)，y為列標(biāo) int dir,corner; //dir為當(dāng)前結(jié)點的方向，corner為拐角次數(shù) };node start; //開始結(jié)點 node ed; //目標(biāo)結(jié)點 注意不要定義成end 杭電和理工都是編譯錯誤，改成ed就好了 int path[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //右、左、下、上 int map[1100][1100],vis[1100][1100]; //原數(shù)組和標(biāo)記數(shù)組 int m,n;void bfs(){queue<node> Q;node cur,pre;start.dir=-1; //始結(jié)點的沒方向，定義為-1 start.corner=0;Q.push(start);while(!Q.empty()){pre=Q.front();Q.pop();if(pre.x==ed.x &&pre.y==ed.y ){ //與目標(biāo)結(jié)點重合既可以消掉 printf("YES\n");return;}for(int i=0; i<4; ++i){cur.x=pre.x+path[i][0];cur.y=pre.y+path[i][1];cur.corner=pre.corner; // 令當(dāng)前節(jié)點的拐點數(shù)和前一個相同 cur.dir=i; //當(dāng)前方向i可以看成上下左右四個方向 if(pre.dir!=cur.dir &&pre.dir!=-1 ){cur.corner++; //始節(jié)點不更新，以后只要和前一個方向不同即可拐點加一 }//判斷是否越界或者拐點數(shù)大于2 if(cur.x<1 || cur.x>n || cur.y<1 || cur.y>m || cur.corner>2)continue;if(map[cur.x][cur.y] && !(cur.x==ed.x && cur.y==ed.y) )continue;//當(dāng)前節(jié)點值非0，但不是 目標(biāo)結(jié)點坐標(biāo) ，不行 //如果新的轉(zhuǎn)折次數(shù)小于以前//訪問時的轉(zhuǎn)折次數(shù)那么更新，否則就不更新。 if(cur.corner<vis[cur.x][cur.y]){vis[cur.x][cur.y]=cur.corner;Q.push(cur);}}}printf("NO\n"); }int main(){int q;while(scanf("%d%d",&n,&m)!=EOF &&n+m ){int i,j;for(i=1; i<=n; ++i )for(j=1; j<=m; ++j)scanf("%d",&map[i][j]);scanf("%d",&q);while(q--){scanf("%d%d%d%d",&start.x, &start.y, &ed.x, &ed.y);if(start.x==ed.x && start.y==ed.y ){//始點和終點相等，不符合 printf("NO\n");continue;}if(!map[start.x][start.y] ||!map[ed.x][ed.y] ||map[start.x][start.y]!=map[ed.x][ed.y]){printf("NO\n");continue;}//開始或結(jié)束位置沒有數(shù)字或者開始和結(jié)束位置的數(shù)字不等。for(i=1; i<=n; ++i)for(j=1; j<=m; ++j)vis[i][j]=INT_MAX;bfs();}}return 0; }

總結(jié)

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

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