信息学奥赛一本通 1252：走迷宫广度优先搜索算法

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。时间限制: 1000 ms内存限制: 65536 KB。空地格子用‘.’表示，有障碍物的格子

长春高老师编程

1195人浏览 · 2024-02-27 16:14:58

长春高老师编程 · 2024-02-27 16:14:58 发布

1252：走迷宫

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入】

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

空地格子用‘.’表示，有障碍物的格子用‘#’表示。

迷宫左上角和右下角都是‘.’。

【输出】

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

【输入样例】

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

【输出样例】

#include<bits/stdc++.h>
using namespace std;
int r, c;
char a[45][45];//地图
struct node {
    int x;//行坐标
    int y;//列坐标
    int step;//第几步
};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void bfs(int x, int y) {
    queue <node> q;
    node t;
    t.x = x;
    t.y = y;
    t.step = 1;
    q.push(t);
    a[1][1] = '#';
    while(!q.empty()) {
        t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (xx==r&&yy==c){//到终点了
                cout<<t.step+1;
                return;
            }
            if (xx >= 1 && xx <= r && yy >= 1 && yy <= c) {
                if (a[xx][yy] == '.') {
                    a[xx][yy] = '#';
                    node tt;
                    tt.x = xx;
                    tt.y = yy;
                    tt.step = t.step+1;
                    q.push(tt);
                }
            }
        }
    }
    return;
}
int main() {
    cin >> r >> c;
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            cin >> a[i][j];
        }
    }
    bfs(1, 1);
    return 0;
}