幾道例題還比較簡單，練習就卡了比較長的時間了(。_。)

所以我會寫一下解題思路了(??д?)
還有博客抽風所以代碼里會有一些奇奇怪怪的東西，無視就好了qwq。

這幾道題我就按各人認為的難易程度來排序吧QAQ。

第一題.

題意：輸入一個迷宮，輸出起點到終點的最短路徑。

輸入：

10
0100110100
0001110010
1000000001
1000100011
0000101100
1000001100
1001010011
0000010100
0101010000
1001000001
1 7 10 2

輸出：

14

解題思路：就是走迷宮233。之前做過的了(⊙o⊙)。

（詳見：http://blog.csdn.net/mr_wuyongcong/article/details/78732439 廣搜例題）

代碼：

#include<cstdio> using namespace std; int n,head,tail,state[1000001][3],x,y,s,py,px; bool walk[1001][1001]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//移動方式 char c; void bfs() {state[1][2]=0;head=0;tail=1;do{head++;//出隊for (int i=0;i<4;i++){x=state[head][0]+dx[i];//位置y=state[head][1]+dy[i];//位置if (walk[x][y] && x>0 && y>0 && x<=n && y<=n)//是否可以通行{tail++;//入隊state[tail][2]=state[head][2]+1;state[tail][0]=x;state[tail][1]=y;walk[x][y]=false;//封閉路線if (x==px && y==py)//判斷終點{s=state[tail][2];return;}}}}while(head<tail);//判斷結束 } int main() {scanf("%d\n",&n);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){c=getchar();if (c=='0') walk[i][j]=true;}c=getchar();} scanf("%d%d%d%d",&state[1][0],&state[1][1],&px,&py); //輸入不解釋bfs();//廣搜不解釋printf("%d",s);//輸出不解釋//就是那么任性QAQ }

第二題：細胞問題（水題）

題目大意：一矩形陣列由數字0到9組成,數字1到9代表細胞,細胞的定義為沿細胞數字上下左右還是細胞數字則為同一細胞,求給定矩形陣列的細胞個數。

輸入：

4 10
0234500067
1034560500
2045600671
0000000089
輸出：

4

解題思路：這道題剛開始做了半天從一個開始搜。后來突然頓悟，為什么不能從多個位置開始搜>(@_@)<。于是就輕輕松松的搞定了233。

代碼：

#include<cstdio> using namespace std; int n,m,s,head,tail,state[2401][2]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//細胞拓展方向 int a[61][61]; char c; void bfs(int x,int y) {head=0;tail=1;state[1][0]=x;state[1][1]=y;do{head++;//出隊for (int i=0;i<4;i++){x=state[head][0]+dx[i];y=state[head][1]+dy[i];if(a[x][y] && x>0 && x<=m && y>0 && y<=n)//如果這里是細胞則往這邊拓展{tail++;//入隊a[x][y]=false;//封閉該位置細胞state[tail][0]=x;state[tail][1]=y;}}}while (head<tail); } int main() {scanf("%d%d\n",&m,&n); for (int i=1;i<=m;i++){for (int j=1;j<=n;j++){c=getchar();if (c!='0') a[i][j]=true;}c=getchar();}//輸入不解釋 for (int i=1;i<=m;i++)for (int j=1;j<=n;j++)//將所有的細胞枚舉一遍{if(a[i][j])//當該處有細胞時數量可以加了{bfs(i,j);//封閉該位置鏈接的細胞s++;//數量加1}}printf("%d",s);//輸出 }

第三題：最小轉彎路徑（難度開始加大了）

題意：給出一個地圖，求起點到終點要轉的最少彎數。

輸入：

5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0 ?
0 0 0 0 1 0 1 ?
0 1 1 0 0 0 0 ?
0 0 0 0 1 1 0?
1 3 1 7?

輸出：

5

附圖：

解題思路：

最小轉彎，不是最少步數。做法比較簡單，不過是把拓展方式從4個方向一個格改成從4個方向撞到墻為止的一次性拓展完。（用老師的說法就是代價相同）

不過注意：封路和墻不要混為一談。因為他是撞到墻才停止拓展，而碰到已經被走過的路只不過是不入隊而不是不繼續拓展。（被卡了好一會qAq）

貼代碼時間：

#include<cstdio> using namespace std; int head,tail,n,m,state[10001][3],c,s,x,y,qx,qy; bool ok[101][101],a[101][101]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//拓展方向 void bfs() {head=0;tail=1;do{head++;//出隊for (int i=0;i<4;i++)//4個方向{x=state[head][0];y=state[head][1];int j=1;while (!a[x+dx[i]*j][y+dy[i]*j] && x+dx[i]*j<=n && y+dy[i]*j<=m && x+dx[i]*j>0 && y+dy[i]*j>0)//如果碰到墻或邊緣就結束拓展{if (!ok[x+dx[i]*j][y+dy[i]*j])//如果已經走過的路線就不入隊{tail++;//入隊state[tail][0]=x+dx[i]*j;state[tail][1]=y+dy[i]*j;//儲存位置state[tail][2]=state[head][2]+1;//儲存轉彎數ok[x+dx[i]*j][y+dy[i]*j]=true;//已經走過該地if (x+dx[i]*j==qx && y+dy[i]*j==qy)//結束判斷{s=state[tail][2];return;}}j++;//下一個拓展}}}while(head<tail);//空隊退出 } int main() {scanf("%d%d\n",&n,&m); for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){scanf("%d",&c);if (c!=0) a[i][j]=true;}}scanf("%d%d%d%d",&state[1][0],&state[1][1],&qx,&qy);//輸入不解釋bfs();//函數不解釋printf("%d",s-1);//輸出不解釋 }
最后的壓軸題：麻將游戲

在一種"麻將"游戲中，游戲是在一個有W＊H格子的矩形平板上進行的。每個格子可以放置一個麻將牌，也可以不放（如圖所示）。玩家的目標是將平板上的所有可通過一條路徑相連的兩張相同的麻將牌，從平板上移去。最后如果能將所有牌移出平板，則算過關。
　　這個游戲中的一個關鍵問題是：兩張牌之間是否可以被一條路徑所連接，該路徑滿足以下兩個特性：
　　1. 它由若干條線段組成，每條線段要么是水平方向，要么是垂直方向。
　　2. 這條路徑不能橫穿任何一個麻將牌 (但允許路徑暫時離開平板)。
　　這是一個例子：

　　在（1，3）的牌和在(4, 4)的牌可以被連接。(2, 3)和(3, 4)不能被連接。
　　你的任務是編一個程序，檢測兩張牌是否能被一條符合以上規定的路徑所連接。?

輸入：輸入文件的第一行有兩個整數w，h （1<=w，h<=75），表示平板的寬和高。接下來h行描述平板信息，每行包含w個字符，如果某格子有一張牌，則這個格子上有個'X'，否則是一個空格。平板上最左上角格子的坐標為（1，1），最右下角格子的坐標為（w,h）。接下來的若干行，每行有四個數x1， y1， x2， y2 ，且滿足1<=x1,x2<=w，1<=y1,y2<=h，表示兩張牌的坐標（這兩張牌的坐標總是不同的）。如果出現連續四個0，則表示輸入結束。

5 4
XXXXX
X ? X
XXX X
?XXX?
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0

輸出：

輸出文件中，對于每一對牌輸出占一行，為連接這一對牌的路徑最少包含的線段數。如果不存在路徑則輸出0。

4

3

0

解題思路：這道題卡了挺久的，近5個小時才做出來。這道題一看就是第三題的升級版，只要注意可以走外圍和每次把封路還原就Ok了o(>﹏<)o

終極代碼時間：

#include<cstdio> using namespace std; int head,tail,state[5930][3],n,m,s,x1,x2,y1,y2; bool a[77][77],walk[77][77]; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//4個方向 char c; void bfs(int x,int y,int px,int py) //計算從(x,y)到(px,py)的最小轉彎數 //這里不講了，詳見第3題 {head=0;tail=1;state[1][0]=x;state[1][1]=y;state[1][2]=0;do{head++;for (int i=0;i<4;i++){x=state[head][0];y=state[head][1];int j=1;while (!a[x+dx[i]*j][y+dy[i]*j] && x+dx[i]*j<=n+1 && y+dy[i]*j<=m+1 && x+dx[i]*j>=0 && y+dy[i]*j>=0){if (!walk[x+dx[i]*j][y+dy[i]*j]){tail++;state[tail][0]=x+dx[i]*j;state[tail][1]=y+dy[i]*j;state[tail][2]=state[head][2]+1;walk[x+dx[i]*j][y+dy[i]*j]=true;if (x+dx[i]*j==px && y+dy[i]*j==py){s=state[tail][2];return;}}j++;}}}while(head<tail); } int main() {scanf("%d%d",&m,&n);//輸入，注意是反過來的c=getchar();//讀第一行的換行符for (int i=1;i<=n;i++){int j=0;while ((c=getchar())!='\n'){j++;if (c=='X') a[i][j]=true;//處理可否通行}} x1=1;while (x1!=0 || y1!=0 || x2!=0 || y2!=0)//如果都為零就退出{scanf("%d%d%d%d",&y1,&x1,&y2,&x2);//輸入，注意是反過來的if (x1!=0 && y1!=0 && x2!=0 && y2!=0)//如果都不為0{for (int i=0;i<=n+1;i++)for (int j=0;j<=m+1;j++) {walk[i][j]=false;}//還原封路s=0;//還原a[x2][y2]=false;//解掉終點的封鎖bfs(x1,y1,x2,y2);//求a[x2][y2]=true;//打開終點的封鎖printf("%d\n",s);}} }

好了，廣搜題目就那么多。↖(^ω^)↗

總結

以上是生活随笔為你收集整理的广搜（练习4题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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