Problem Description

2020級的新生即將來USST報道了，學校規定報道地點定在了516號的老體育館。

現在為了方便新生報道，Wiki自我推薦為新生繪制一張校園地圖。地圖功能很簡單：假設校園是一張二維的平面圖，大小為n × m，校園的建筑在地圖上用任意字符表示，如果遇到不能前行的障礙物則用字符N表示，設起點為S,報道點為G，請你幫助Wiki計算出最短的報道距離以及該條最短路徑上的點坐標。

如果存在多條的最短報道路徑，輸出任意一條即可。（假設可以在地圖“上下左右”四個方向上行走，且必存在到達路線）

Input

第一行輸入兩個正整數n和m(2 <= n, m <= 100)，表示地圖的大小

第二行開始輸入n行m列的建筑物字符標識（字符釋義見上述題面）

Output

輸出第一行一個正整數ans，表示從起點S到終點G的最短距離

第二行開始輸出最短路徑經過的建筑物坐標(xi, yi)，輸出一個換一行，起點和終點坐標也要輸出！假設坐標原點為(0, 0)

Sample Input：

3 3 S.. NN. G..

Sample Output：

6 0 0 0 1 0 2 1 2 2 2 2 1 2 0

分析
BFS，記錄路徑。
此處使用兩個數組px[dx][dy]=x和py[dx][dy]=y來記錄點(dx,dy)的前面一點(x,y).

#include<iostream> #include<queue> #include<cstring>using namespace std;const int maxn=200;int m,n,t1,t2,d1,d2;//起點和終點 char a[maxn][maxn]; bool vis[maxn][maxn];//表示是否訪問過 int dis[4][2]={1,0,0,1,-1,0,0,-1};//四個方向 int len[maxn][maxn];//保存起點到任何點的最小距離 int px[maxn][maxn],py[maxn][maxn];//記錄最短路徑 queue<pair<int,int> > q;void bfs(){q.push(make_pair(t1,t2));vis[t1][t2]=1;while(!q.empty()){int x=q.front().first;int y=q.front().second;q.pop();if(x==d1&&y==d2) return;for(int i=0;i<4;i++){int dx=x+dis[i][0];int dy=y+dis[i][1];if(dx>=0&&dx<m&&dy>=0&&dy<n&&!vis[dx][dy]&&a[dx][dy]!='N'){if(len[dx][dy]>len[x][y]+1)//距離小者更新 {len[dx][dy]=len[x][y]+1;//長度 q.push(make_pair(dx,dy));//入隊 vis[dx][dy]=1;//訪問過 //v.push_back(make_pair(dx,dy));//保存路徑 px[dx][dy]=x;py[dx][dy]=y;//前一個坐標 } }} } }void print(int x,int y){if(x!=-1&&y!=-1){//遞歸出口，到達起點 print(px[x][y],py[x][y]);//如果把遞歸放后面，則是倒序輸出 if(x==d1&&y==d2) cout<<x<<" "<<y;//不能輸出多余的換行符 else cout<<x<<" "<<y<<endl;}}int main(){memset(len,0x3f,sizeof(len));//距離無窮大 memset(vis,0,sizeof(vis));//表示沒訪問過 memset(px,-1,sizeof(px));memset(py,-1,sizeof(py));cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>a[i][j]; if(a[i][j]=='S')t1=i,t2=j;//起點 if(a[i][j]=='G')d1=i,d2=j;//終點 }len[t1][t2]=0;//起點距離為0 bfs(); cout<<len[d1][d2]<<endl;print(d1,d2);}

遞歸打印的寫法
從終點到起點print(d1,d2)，由于棧的后進先出特性，遞歸最后的先返回，于是正好是先返回起點，依次到終點。

void print(int x,int y){if(x!=-1&&y!=-1){//遞歸出口，到達起點 print(px[x][y],py[x][y]);//如果把遞歸放后面，則是倒序輸出 if(x==d1&&y==d2) cout<<x<<" "<<y;//不能輸出多余的換行符 else cout<<x<<" "<<y<<endl;}}

總結

以上是生活随笔為你收集整理的BFS最短路打印路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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