題目：

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

分析與解答：

這個題需要考慮轉向，轉向的話就是根據到當前數走的方向與到上個數走的方向是否相同來判斷。如果不同，轉彎的數要加一。現在我們有坐標，方向轉彎次數就好寫了，其中我們認為方向0就是向下，1向右，2向上，3向左，-1是最初的x1y1的方向，意味著從他走向下一個數是不用考慮轉彎的，只用記錄到達這個數的方向
由于他是詢問x1y1到x2y2，我們只需判斷是否有x1y1到x2y2的路，這個題讓我刷新了對標記數組的認識，之前的標記數組都是經過了就變為另一個數，下次在經過這個坐標時如果已做過標記就不走。但這個是用于記錄從（x1，y1）到（i，j）轉彎的最小次數，如果在（i，j）這個位置的step<=v[i][j],就push到隊列里，我試了一下，如果把這個標志數組去掉就會超時，就是從起點到一個點的的路徑有多條，但是如果只是說經過了就不再考慮到這個點的其他路徑的話，這個點到終點的轉彎次數加上起點到這個點的轉彎次數會超過二，這是不滿足題意的，所以我們到這個點之后還需要考慮其他到這個點的路徑，其唯一目的就是讓從起點到終點的路徑轉彎的次數最小，這樣的話，就有極大的可能從這個路徑一直走到終點的過程中轉彎的次數滿足題意，所以我們標記數組只存最小或者等于目前最小的轉彎次數的路徑
前面還有個判斷，如果step比2小，就繼續搜索，這是題目要求
還有常規判斷，走一步之后新的坐標在范圍內，新坐標這個位置沒有棋子，這個新坐標就是我們要找的坐標 ，滿足這寫條件，此時我們再考慮是不是該push了

參考代碼：
https://blog.csdn.net/jzmzy/article/details/16862263

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define MAXN 1005 using namespace std; int map[MAXN][MAXN],v[MAXN][MAXN]; const int dx[4] = {0,1,0,-1}; const int dy[4] = {-1,0,1,0}; int n,m,flag; struct node {int x,y;int dir;//記錄方向int step;//記錄轉彎次數 }; int bfs(int x1,int y1,int x2,int y2) {memset(v,11,sizeof(v));//標志數組 記錄某條路徑在該點轉向的次數queue <node> q;node s,temp;s.x = x1;s.y = y1;s.dir = -1;//-1表示朝哪個方向都可以s.step = 0;q.push(s);while(!q.empty()){temp = q.front();q.pop();if(temp.x == x2 && temp.y == y2 && temp.step <= 2)return 1;for(int i = 0; i < 4; i ++){s = temp;s.x += dx[i];s.y += dy[i];//走一步之后新的坐標在范圍內，而且只有當坐標這個位置沒有棋子或者說這個坐標就是我們要找的坐標 if(s.x >= 1 && s.x <= n && s.y >= 1 && s.y <= m && (map[s.x][s.y] == 0 || (s.x == x2 && s.y == y2))){if(s.dir != -1)//s.dir是上上個坐標走到上個坐標的方向，這個坐標要從新記錄 {if(s.dir != i)//與上個坐標的方向相反，就說明轉彎了 {s.dir = i;s.step ++;}}else s.dir = i;//記錄走的方向 if(s.step > 2) continue;if(s.step <= v[s.x][s.y])//保證轉彎次數最少，等號不能忘記{v[s.x][s.y] = s.step;q.push(s);}}}}return 0; } int main() {int i,j,t,x1,y1,x2,y2;while(scanf("%d%d",&n,&m),(n+m)){for(i = 1; i <= n; i ++)for(j = 1; j <= m; j ++)scanf("%d",&map[i][j]);//n行m列的圖 scanf("%d",&t);while(t--)//從、詢問 {scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//坐標相同，或者數不同，或者沒有東西 if(!map[x1][y1] || !map[x2][y2] || map[x1][y1] != map[x2][y2] || (x1 == x2 && y1 == y2) )flag = 0;else flag = bfs(x1,y1,x2,y2);if(flag) puts("YES");else puts("NO");}}return 0; }

總結

以上是生活随笔為你收集整理的（bfs）连连看（hdu1175）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。