bfs--acwing

题目一：走迷宫

844. 走迷宫 - AcWing题库

分析

bfs 求最小步数

地图用二维存储，标记因为地图是01，一起使用。

步数与移动状态（坐标）的关系，可以用映射map，或者二维数组，或者结构体。

也可以用变量存步数（这个我弄的容易出bug）

代码（map)

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
using PII = pair<int,int>;
int n, m;
int arr[N][N];

map<PII,int> ans; // 或者使用二维数组来映射步数

int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};

void bfs() {
    queue<PII> q;
    q.push({0,0});
    ans[{0,0}] = 0;
    arr[0][0] = 1;
    
    while(q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first,  y = t.second;
        
        for(int i = 0; i < 4; i ++) {
            int a = x+dx[i], b = y+dy[i];
            if(!arr[a][b] && a>=0 && b>=0 && a<n && b<m) {
                arr[a][b] = 1;
                q.push({a,b}); ans[{a,b}] = ans[{x,y}]+1;
            }
        }
        
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) 
        for(int j = 0; j < m; j ++)
            cin >> arr[i][j];
    
    bfs();
    
    cout << ans[{n-1,m-1}] << endl;
    
    return 0;
}

代码（变量存储步数）

#include<bits/stdc++.h>
using namespace std;

using PII = pair<int,int>;
const int N = 110;
int arr[N][N];
int ans;
int n, m;

int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};

void bfs() {
    queue<PII> q;
    q.push({0,0});
    arr[0][0] = 1;
    
    int ed = 1, cnt = 1,idx = 0; ans = 0;
    while(q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;
        idx ++;
        for(int i = 0; i < 4; i ++) {
            int a = x+dx[i], b = y+dy[i];
            if(!arr[a][b] && a>=0 && b>=0 && a<n && b<m) {
                cnt ++;
                q.push({a,b}); 
                arr[a][b] = 1; 
                
            }
        }
        
        if(x==n-1 && y==m-1) return ;
        if(idx==ed) {
            ed = cnt; ans ++;
        }
        
    }
    
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) 
        for(int j = 0; j < m; j ++) 
            cin >> arr[i][j];
    
    bfs();
    
    cout << ans << endl;
    
    return 0;
}