ACWing844. 走迷宫

题目

分析

最短路，权值相同，用BFS

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 const int N = 110;
 8 int n ,m;
 9 int g[N][N],d[N][N]; //g表示地图，d表示从(0,0)到(i，j)最短路径距离
10 typedef pair<int,int>PII; //二维坐标
11 queue<PII>q;//队列
12 //定义方向，上下左右(0,1)、(0,-1)、(-1,0)、(1,0)
13 //int dx[4] = {0,0,-1,1},dy[4] = {1,-1,0,0};
14 pair<int,int>dd[4] = {{0,1},{0,-1},{-1,0},{1,0}};
15 
16 int bfs(){
17     d[0][0] = 0;
18     q.push({0,0});
19     while(!q.empty()){
20         auto t= q.front();
21         q.pop();
22         for(int i = 0;i < 4;i++){
23             //int x = t.first + dx[i],y = t.second + dy[i];
24             int x = t.first + dd[i].first,y = t.second + dd[i].second;
25             if(g[x][y] == 0 && d[x][y] == -1 && x < n && y < m && x >= 0 && y >= 0){
26                 d[x][y] = d[t.first][t.second] + 1;
27                 q.push({x,y});
28             }
29         }
30     }
31     return d[n-1][m-1];
32 }
33 
34 int main(){
35    cin>>n>>m;
36    for(int i = 0;i < n;i++){
37        for(int j = 0;j < m;j++){
38            cin>>g[i][j]; 
39        }
40    }
41    memset(d,-1,sizeof(d));//从起点到每个位置初始化为-1，表示未访问。
42    printf("%d",bfs());
43    return 0;
44 }

输出路径

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 const int N = 110;
 8 int n ,m;
 9 int g[N][N],d[N][N]; //g表示地图，d表示从(0,0)到(i，j)最短路径距离
10 typedef pair<int,int>PII; //二维坐标
11 queue<PII>q;//队列
12 //定义方向，上下左右(0,1)、(0,-1)、(-1,0)、(1,0)
13 //int dx[4] = {0,0,-1,1},dy[4] = {1,-1,0,0};
14 pair<int,int>dd[4] = {{0,1},{0,-1},{-1,0},{1,0}};
15 
16 //记录路径
17 PII pre[N][N];
18 
19 int bfs(){
20     d[0][0] = 0;
21     q.push({0,0});
22     while(!q.empty()){
23         auto t= q.front();
24         q.pop();
25         for(int i = 0;i < 4;i++){
26             //int x = t.first + dx[i],y = t.second + dy[i];
27             int x = t.first + dd[i].first,y = t.second + dd[i].second;
28             if(g[x][y] == 0 && d[x][y] == -1 && x < n && y < m && x >= 0 && y >= 0){
29                 d[x][y] = d[t.first][t.second] + 1;
30                 q.push({x,y});
31                 pre[x][y] = t;//记录从哪里转移过来的
32                 
33             }
34         }
35     }
36     return d[n-1][m-1];
37 }
38 
39 int main(){
40    cin>>n>>m;
41    for(int i = 0;i < n;i++){
42        for(int j = 0;j < m;j++){
43            cin>>g[i][j]; 
44        }
45    }
46    memset(d,-1,sizeof(d));//从起点到每个位置初始化为-1，表示未访问。
47    printf("%d",bfs());
48    
49    //逆序打印路径
50    int x = n-1,y = m-1;
51    while(x || y){
52        cout<<x<< " " <<y<<endl;
53        x = pre[x][y].first, y = pre[x][y].second;
54        
55    }
56    return 0;
57 }