BFS 广度优先搜索

image-20250121225011054

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

int g[110][110];
int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int dist[110][110]; //距离
typedef pair<int,int> PII; //x,y

queue<PII> q;


int bfs(int x,int y) {
    memset(dist,-1,sizeof dist);
    q.push({x,y});
    dist[x][y] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (g[a][b] != 0) continue;
            if (dist[a][b] > 0) continue;
            dist[a][b] = dist[t.first][t.second] + 1;
            q.push({a,b});
            if (a == n && b == m) return dist[a][b];
        }
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> g[i][j];
        }
    }
    int res = bfs(1,1);
    cout << res;
}