【C++板块提升计划】每周一练第六期 BFS练习2【代码含注释讲解】

zhangjinxuan

大家好，今天是每周一练的第6期数期

这次的每周一练由我帮助用户@高山 发帖

题目名称：BFS练习2

题目说明：
给你一个n×m的矩形，#表示墙不能通过，S表示起点(可以通过)，.表示空地。你每次可以沿着上下左右四个方向移动。
问从S点出发，到达所有点最少需要移动多少次。

输入说明：
第一行，两个整数n,m。
接下来n行，每行一个长度为m的字符串。

输出说明：
一共n行m列，每个数表示移动到对应位置需要多少步，如果是墙或者无法到达，输出-1。

样例输入

5 5
.#.#.
.###.
..S#.
.##..
.....

样例输出

4 -1 -1 -1 12
3 -1 -1 -1 11
2 1 0 -1 10
3 -1 -1 8 9
4 5 6 7 8

数据规模
对于所有数据，保证1≤n,m≤200，恰好有一个S。

测试链接：评论区发布

参考代码：

#include <cstdio>
#include <cstring>

using namespace std;

int res[201][201], s_x, s_y, n, m; //res_i_j表示从起点到i_j所需步数，s_x和s_y，不要误会，这是起点坐标，n,m表示矩阵大小
char map[201][201]; //整个地图
int queue[40200][2], front = 1, rear = 0; //队列，队首，队尾，都先要初始化，因为遍历的点数是n*m个，所以队列大小是比n*m最大时要多的
int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; //四个方向

void add(int x, int y) { //加入队列，此函数用的不频繁，可以不写函数
        queue[++rear][0] = x;
        queue[rear][1] = y; //只能加一次rear!!!
}

int main() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
                getchar(); //过滤换行
                for (int j = 1; j <= m; ++j) {
                        scanf("%c", &map[i][j]);
                        if (map[i][j] == 'S') //如果是起点
                                s_x = i, s_y = j; //更新坐标
                }
        }
        add(s_x, s_y); //一定要把起点加入队列！！
        memset(res, 255, sizeof(res)); //res全部初始化为-1
        res[s_x][s_y] = 0; //起点到起点步数肯定是0啊
        while (rear + 1 != front) { //非空时执行
                int top_x = queue[front][0], top_y = queue[front++][1]; //获取队首
                for (int i = 0; i < 4; ++i) { //枚举四个方向
                        int new_x = dir[i][0] + top_x, new_y = dir[i][1] + top_y, step = res[top_x][top_y] + 1; //获取新坐标
                        if (map[new_x][new_y] == '.' && res[new_x][new_y] == -1) { //判断合法性
                                add(new_x, new_y); //加入队列
                                res[new_x][new_y] = step; //更新答案
                        }
                }
        }
        for (int i = 1; i <= n; ++i) { //答案输出
                for (int j = 1; j <= m; ++j)
                        printf("%d ", res[i][j]);
                puts("");
        }
}

上一篇：把字符变得一样
下一篇：推箱子

说明：题目来源于 代码源 链接：http://oj.daimayuan.top/

高山

演示视频请戳我

zhangjinxuan

推荐测试链接：http://oj.daimayuan.top/problem/148

hveagle

@高山

zhangjinxuan

@高山
Where are you now? (你在哪？）
Atlantis~（高山）
Under the sea? （在潜水吗？）
Under the sea~e （不在线吗？）
Where are you now? （你在哪儿？）
Another dream~ （又一天过去了）
The monsters running wild inside of me （着急在我身体内狂奔）
I'm faded （我很着急）
I'm faded （我很着急）
So lost （我十分着急）
I'm faded （我很着急，人去哪儿了？）

哈哈哈哈哈哈哈哈哈哈哈~

zhangjinxuan

sorry，在审核，不知触发了什么敏感关键词....

zhangjinxuan

说明一下，题目转载于代码源