ACWING-844-走迷宫

广度优先

#include 
using namespace std;
typedef pair PII;
const int N = 110;

int n, m;

int g[N][N]; //地图
int f[N][N]; //距离
PII q[N*N];  //模拟队列

int n,m;

void bfs (int a, int b)
{
    queue q;

    q.push({a, b});
    
    while (!q.empty())
    {   // 1. 取出来第一个
        PII start = q.front();
        q.pop();
        g[start.first][start.second] = 1;
        int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
        // 2. 遍历四个方向
        for (int i = 0; i < 4; i ++)
        {
            int x = start.first + dx[i], y = start.second + dy[i];
            // 3. 如果是墙壁的话
            if (g[x][y] == 0)
            {
                g[x][y] = 1;
                // 4. //从当前点走过去，则距离等于当前点的距离+1？
                f[x][y] = f[start.first][start.second] + 1;
                q.push({x, y});
            }
        }
    }
    cout << f[n][m];
}
int main() {
    memset(g, 1, sizeof(g));
    cin >> n >> m;

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> g[i][j];
    bfs(1, 1);
    return 0;
}

···