题目描述

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0
或 1
，其中 0
表示可以走的路，1
表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1)
处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)
处，至少需要移动多少次。

数据保证 (1,1)
处和 (n,m)
处的数字为 0
，且一定至少存在一条通路。

样例输入

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

8

BFS:

还是可以想到使用bfs的, 非y总写法:

C++ 代码

#include <iostream>
#include <queue>
#include <bits/ios_base.h>

using namespace std;

const int N = 110;
int n, m;
int Map[N][N];
bool vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node {
    int x, y, cnt;
};

queue<node> q;

void bfs() {
    node a;
    a.x = 1, a.y = 1, a.cnt = 0;
    q.push(a);
    vis[1][1] = true;
    while (!q.empty()) {
        for (int i = 0; i < 4; i ++) {
            int bx = q.front().x + dx[i];
            int by = q.front().y + dy[i];
            node b;
            b.x = bx, b.y = by, b.cnt = q.front().cnt + 1;
            if (bx > 0 && bx <= n && by > 0 && by <= m && Map[bx][by] == 0 && !vis[bx][by]) {
                q.push(b);
                if (bx == n && by == m) {
                    cout << b.cnt << "\n";
                    return ;
                }

                vis[bx][by] = true;
            }
        }

        q.pop();   
    }

    cout << 0 << "\n";
    return ;
}

signed main(int argc, const char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> Map[i][j];
        }
    }

    bfs();

    return 0;
}