题目描述

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

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

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

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

输入格式
第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100

输入样例

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

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII; //相当于结构体

const int N = 110;
int n,m;
int g[N][N];    //存储图
int d[N][N];    //存储d[x][y] 到 起点 的距离

int dfs()
{
    queue<PII> q;  // 创建可以存<int,int> 的队列

    memset(d,-1,sizeof(d));   //memset(void *buffer, int c, int count)
    //，其中buffer为指针或是数组，c是赋给buffer的值
    //，count是buffer的长度。c++中，头文件<cstring>。按字节赋值

    d[0][0] = 0;  //标记 这个点已走过
    q.push({0,0});   // 将起点压入队列

    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1}; //分别对应某点处可扩展的方向：
    //上:(-1,0) 右:(0,1) 下:(1,0) 左:(0,-1)

    while(q.size())  // 如果队列不空
    {
        auto t = q.front();  // front() 返回队头元素
        q.pop();                // 弹出队头元素
        for(int i = 0;i<4;i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];   // 将当前节点下标 + 偏移量，
            //获得下一节点的下标; first 、second 分别对应 PII 中的第一个值、第二个值；


            //if判断：若下标没超出地图范围 且 g[x][y] == 0 且 这个点没走过
            // 则： 从起点走到(x, y)的步数等于从起点走到(t.first, t.second)的步数加一，
            // 因为我们是从(t.first, t.second)都到(x, y)的
            // 将{x,y} 压入队列
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x,y});
            }
        }

    }
    return d[n-1][m-1];
    //每行每列都是从下标0开始存储的，下标[n-1][m-1]对应最右下角的位置
}


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

    cout<<dfs()<<endl;
    return 0;
}