C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e2 + 10;
int g[N][N];    //记录迷宫内位置
int d[N][N];    //到原点距离
typedef pair<int, int> pii; //二元组记录x,y
pii q[N * N];   //bfs需要用到队列，因为是pii型的，所以可能有N*N的种类，数组要开大些
pii prepath[N][N];  //记录当前点的上一个点，即可以记录经过的路径
int n, m;
int bfs(void)
{
    memset(d, -1, sizeof(d));   //初始化d
    q[0] = {0, 0};  //先把原点放入队列中
    d[0][0] = 0;    //原点到原点的距离要置成0
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   //偏移量，左上右下
    int hh = 0, tt = 0; //初始化队头，队尾指针
    while(hh <= tt){    //队列要用while循环hh <= tt来控制
        pii t = q[hh ++];   //出队，特殊，hh,tt都是向右移动，窗口向右移动
        for(int i = 0; i < 4; ++i){     //4个方向都做判断，选择最短的
            int x = t.first + dx[i], y = t.second + dy[i];  //移动
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){    //不出界且可走且之前没走过，如果之前走过的话那这必不是最短路
                q[++ tt] = {x, y};  //入队
                d[x][y] = d[t.first][t.second] + 1; //更新距离
                prepath[x][y] = t;  //记录当前点的上一个点
            }
        }
    }
    int x = n - 1, y = m - 1;
    while(x || y){  //由后到前输出移动路径
        printf("(%d %d)<-", x, y);
        pii t = prepath[x][y];
        x = t.first, y = t.second;
    }
    cout << endl;
    return d[n-1][m-1];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            scanf("%d", &g[i][j]);
    printf("%d\n", bfs());
    return 0;
}