bfs走迷宫

重点
1. 宽搜最经典的应用场景是解决最短路问题
2. 注意队列中的元素是什么

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;

int a[N][N];
int n, m;
int st[N][N];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

int bfs() {  // 宽搜
    queue<PII> q;
    memset(st, -1, sizeof(st));  // st状态标记，-1表示没有搜索过，其他表示搜到这个点需要多少步
    q.push({0, 0}); // 源点入队列
    st[0][0] = 0;  // 源点的步数为0

    while (!q.empty()) {  // 当队列中不为空时，从队列中区出一个点进行扩展
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x < 0 || y < 0 || x >= n || y >= m) continue;
            if (a[x][y] == 1 || st[x][y] != -1) continue;
            st[x][y] = st[t.first][t.second] + 1;
            if (x == n - 1 && y == m - 1) return st[x][y];
            q.push({x, y});
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j] ;
        }
    }

    int t = bfs();  
    cout << t << endl;

    return 0;
}