正題

---

題目大意

$n?m$的地圖，每個格子有限制。是障礙的話就不可以到，如果不是就會要求在這個格子不可以像上下左右其中一個方位走。求最少拐彎次數。

---

解題思路

就是bfs，之前寫過類似的，詳見：https://blog.csdn.net/Mr_wuyongcong/article/details/78755411

---

code

#include<cstdio> #include<queue> #include<algorithm> #include<iostream> #define N 510 using namespace std; const int dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1}; struct node{int x,y,w; }; queue<node> q; int a[N][N],path[N][N],n,m; char c; int bfs() {q.push((node){1,1,-1});while(!q.empty()){int x=q.front().x,y=q.front().y,w=q.front().w;q.pop();for(int k=1;k<=4;k++){int dis=1;while(x+dx[k]*dis<=n&&x+dx[k]*dis>0&&y+dy[k]*dis<=m&&y+dy[k]*dis>0&&a[x+dx[k]*(dis-1)][y+dy[k]*(dis-1)]!=k&&a[x+dx[k]*dis][y+dy[k]*dis])//判斷的是否可行{if(!path[x+dx[k]*dis][y+dy[k]*dis])//已經走過{q.push((node){x+dx[k]*dis,y+dy[k]*dis,w+1});path[x+dx[k]*dis][y+dy[k]*dis]=1;//標記if(x+dx[k]*dis==n&&y+dy[k]*dis==m)//到達return w+1;}dis++;}}}return -1; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>c;if(c=='U') a[i][j]=1;else if (c=='D') a[i][j]=3;else if (c=='L') a[i][j]=2;else if (c=='R') a[i][j]=4;}//輸入a[n][m]=4;//防止終點是障礙物int ans=bfs();if(ans==-1) printf("No Solution");else printf("%d",ans); }

總結

以上是生活随笔為你收集整理的nssl1175-小S练跑步【bfs】的全部內容，希望文章能夠幫你解決所遇到的問題。

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