题目描述

一个迷宫由 R行 C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。
只能在水平方向或垂直方向走，不能斜着走。

样例

5 5
..###
#....
#.#.#
#.#.#
#.#..

算法 广搜bfs

详情见注释

时间复杂度

参考文献

C++ 代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int>PII;
const int N = 40;
char mp[N][N];//迷宫地图
int d[N][N];//步数
queue<PII>q;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };//表示方向
int n,m;
int  bfs(int x,int y) {
    q.push({x,y});
    mp[x][y] = '#';
    d[x][y] = 1;//起点也有步数，步数为1
    while (q.size()) {//经典bfs模板
        PII t = q.front();
        int xx = t.first,yy = t.second;
        q.pop();
        if (xx == n - 1 && yy == m - 1) {
        return d[xx][yy];//到达右下角是输出
    }
        for (int i = 0; i < 4; i++) {
        int nx = xx + dx[i];
        int ny = yy + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] == '.') {
            mp[nx][ny] = '#';

            d[nx][ny] = d[xx][yy] + 1;q.push({nx,ny});
        }
    }
    }
    return -1;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
        }
    cout<<bfs(0,0);


    return 0;
}

（纯蒟蒻的第一篇题解）