题目描述

走迷宫

样例

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

算法1

用 g[n][m] 存储地图，f[n][m] 存储起点到 n,m 的距离。

从起点开始广度优先遍历地图。

当地图遍历完，就求出了起点到各个点的距离，输出f[n][m]即可。

C++ 代码1结构体（注释是数组模拟队列）

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

struct pairr {  //typedef pair<int,int> PII;
    int x;
    int y;
};

const int N =110;
int n,m;
int g[N][N],d[N][N];
struct pairr q[N * N];  //PII q[N * N];

int bfs() {
    int hh=0,tt=0;
    q[0]= {0,0};

    memset(d,-1,sizeof d);
    d[0][0]=0;

    int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

    while(hh<=tt) {
        struct pairr t=q[hh++ ];  //auto t=q[hh++ ];

        for(int i=0; i<4; i++) {
            int x=t.x+dx[i],y=t.y+dy[i];  //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) {
                d[x][y]=d[t.x][t.y]+1;  //d[x][y]=d[t.first][t.second]+1;
                q[++tt]= {x,y};
            }
        }
    }

    return d[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<<bfs()<<endl;

    return 0;
}

C++ 代码2队列

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N], d[N][N];
queue<PII> q;

int bfs() {
    q.push({0, 0});
    memset(d, -1, sizeof(d));
    d[0][0] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (q.size()) { //队列不为空
        PII t = q.front();//取队头元素
        q.pop();//出队
        for (int i = 0; i < 4; i++) {
            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) {
                d[x][y] = d[t.first][t.second] + 1;//当前点到起点的距离
                q.push({x, y});//将新坐标入队
            }
        }
    }
    return d[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 << bfs() << endl;
    return 0;
}