總結

bfs除了代碼能力沒有任何算法。。。
有些細節是值得注意的

T1 面積(area)

bfs被我寫成了dfs。。。
（不過我覺得這么寫挺不戳）
核心思路就是用一個flag記錄當前跑得這些點有沒有效
惡心之處在于本題默認m=n=10！！！

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #define ll long long using namespace std; const int N=1e6+100; int m,n; int mp[1001][1001],jd[1001][1001]; int flag=1; int xx[5]={0,0,0,1,-1},yy[5]={0,1,-1,0,0}; int dfs(int x,int y){if(jd[x][y]) return 0;if(x<1||x>n||y<1||y>m){flag=0;return 0;}if(mp[x][y]) return 0;jd[x][y]=1;int ans=1;for(int i=1;i<=4;i++) ans+=dfs(x+xx[i],y+yy[i]);if(flag) return ans;else return 0; } int main(){n=10;m=10;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]);}int tot=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){flag=1;tot+=dfs(i,j);}}printf("%d",tot); } /* 10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 04 6 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 */

T2 營救

too water too say anything…
（就是簡單的寬搜）

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<queue> #define ll long long using namespace std; const int N=1e6+100; int m,n; int xx0,yy0,X,Y; int mp[1010][1010],jd[1010][1010]; int flag=1; int xx[5]={0,0,0,1,-1},yy[5]={0,1,-1,0,0}; struct node{int x,y,step; }; void bfs(){queue<node>q;q.push((node){xx0,yy0,0});while(!q.empty()){node o=q.front();q.pop();if(o.x==X&&o.y==Y){printf("%d",o.step);return;}for(int i=1;i<=4;i++){int nx=o.x+xx[i],ny=o.y+yy[i];if(mp[nx][ny]||jd[nx][ny]||nx<1||nx>n||ny<1||ny>n)continue;jd[nx][ny]=1;q.push((node){nx,ny,o.step+1}); }}return; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) scanf("%1d",&mp[i][j]);}scanf("%d%d%d%d",&xx0,&yy0,&X,&Y);bfs(); } /* 3 001 101 100 1 1 2 24 6 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 */

T3 最少轉彎問題(turn)

代碼也與上一題類似
只是把每次嘗試入隊的元素改成一整排就行了
注意：只走一行的話應該算0次轉彎，所以初始入隊元素要從-1開始記錄次數

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<queue> #define ll long long using namespace std; const int N=1e6+100; int m,n; int xx0,yy0,X,Y; int mp[1010][1010],jd[1010][1010]; int flag=1; int xx[5]={0,0,0,1,-1},yy[5]={0,1,-1,0,0}; struct node{int x,y,step; }; void bfs(){queue<node>q;q.push((node){xx0,yy0,-1});while(!q.empty()){node o=q.front();q.pop();if(o.x==X&&o.y==Y){printf("%d",o.step);return;}for(int i=1;i<=4;i++){int nx=o.x,ny=o.y;while(1){nx+=xx[i];ny+=yy[i];if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]||jd[nx][ny]) break;q.push((node){nx,ny,o.step+1});jd[nx][ny]=1;} }}return; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%1d",&mp[i][j]);}scanf("%d%d%d%d",&xx0,&yy0,&X,&Y);bfs(); } /* 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 */

T4 麻將游戲(mahjong)

這題也和上一題類似（本次模擬還真是循序漸進。。。）
不同是這個初始從1開始
另外這個可以走到棋盤外面，所以邊界條件要改一下
（本題輸入空格有些惡心，我使用的是直接gets）（getchar一知半解）

重點！！：

本題中我一開始的寫法是：

while(1){nx+=xx[i];ny+=yy[i];if(nx==X&&ny==Y){ans=min(ans,o.step+1);}if(nx<0||nx>n+1||ny<0||ny>m+1||mp[nx][ny]=='X'||jd[nx][ny]) break;q.push((node){nx,ny,o.step+1});jd[nx][ny]=1;}

但是這樣會有大問題！！！
jd判斷賦過值只意味著改點不用更新，但它后面的點仍然可能更新
所以這種情況下應該是continue而非break！！！
所以

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<queue> #define ll long long using namespace std; const int N=1e6+100; int m,n; int xx0,yy0,X,Y; char mp[1010][1010]; int jd[1010][1010]; int flag=1; int xx[5]={0,0,0,1,-1},yy[5]={0,1,-1,0,0}; struct node{int x,y,step;bool operator < (node y)const{return step>y.step;} }; void bfs(){priority_queue<node>q;q.push((node){xx0,yy0,0});int ans=2e9;while(!q.empty()){node o=q.top();q.pop();for(int i=1;i<=4;i++){int nx=o.x,ny=o.y;while(1){nx+=xx[i];ny+=yy[i];if(nx==X&&ny==Y){ans=min(ans,o.step+1);}if(nx<0||nx>n+1||ny<0||ny>m+1||mp[nx][ny]=='X') break;if(jd[nx][ny]) continue;q.push((node){nx,ny,o.step+1});jd[nx][ny]=1;} }}if(ans==2e9) printf("0\n");else printf("%d\n",ans);return; } int main(){//本題xy坐標相反！ scanf("%d%d\n",&m,&n);for(int i=1;i<=n;i++){gets(mp[i]+1);}while(1){scanf("%d%d%d%d",&yy0,&xx0,&Y,&X);if(xx0==0){// printf("ksdhf");break;}memset(jd,0,sizeof(jd));bfs();}return 0; } /* 5 5 X X X X XX XXXXX 1 1 4 4 */

總結

以上是生活随笔為你收集整理的4.6模拟 宽度优先搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

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