题目描述

给定一个n*m的二维整数数组，用来表示一个迷宫
最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1000

思路

广度优先遍历：
用 g[n][m] 存储地图，f[n][m] 存储起点到 n,m 的距离。
从起点开始广度优先遍历地图。
当地图遍历完，就求出了起点到各个点的距离，输出f[n][m]即可
现在假设0是可以走的，1是不能走的，方便作图 
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N];//存储地图
int f[N][N];//存储距离
int n, m;
void bfs(int a, int b)//广度优先遍历
{
    queue<PII> q;
    q.push({a, b});
    while(!q.empty())
    {
        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};
        for(int i = 0; i < 4; i++)//往四个方向走
        {
            int x = start.first + dx[i], y = start.second + dy[i];
            if(g[x][y] == 0)//如果还没有走过
            {
                g[x][y] = 1;
                f[x][y] = f[start.first][start.second] + 1;//从当前点走过去，则距离等于当前点的距离+1.
                q.push({x, y});
            }

        }
    }
    cout << f[n][m];
}

int main()
{
    memset(g, 1, sizeof(g));
    cin >> n >>m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
        }
    }
    bfs(1,1);

}