【C++板块提升计划】每周一练第六期 BFS练习2【代码含注释讲解】
本帖最后由 zhangjinxuan 于 2022-10-27 20:11 编辑大家好，今天是每周一练的第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, s_x, s_y, n, m; //res_i_j表示从起点到i_j所需步数，s_x和s_y，不要误会，这是起点坐标，n,m表示矩阵大小
char map; //整个地图
int queue, front = 1, rear = 0; //队列，队首，队尾，都先要初始化，因为遍历的点数是n*m个，所以队列大小是比n*m最大时要多的
int dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; //四个方向
void add(int x, int y) { //加入队列，此函数用的不频繁，可以不写函数
queue[++rear] = x;
queue = 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);
if (map == 'S') //如果是起点
s_x = i, s_y = j; //更新坐标
}
}
add(s_x, s_y); //一定要把起点加入队列！！
memset(res, 255, sizeof(res)); //res全部初始化为-1
res = 0; //起点到起点步数肯定是0啊
while (rear + 1 != front) { //非空时执行
int top_x = queue, top_y = queue; //获取队首
for (int i = 0; i < 4; ++i) { //枚举四个方向
int new_x = dir + top_x, new_y = dir + top_y, step = res + 1; //获取新坐标
if (map == '.' && res == -1) { //判断合法性
add(new_x, new_y); //加入队列
res = step; //更新答案
}
}
}
for (int i = 1; i <= n; ++i) { //答案输出
for (int j = 1; j <= m; ++j)
printf("%d ", res);
puts("");
}
}
上一篇：把字符变得一样
下一篇：推箱子
说明：题目来源于 代码源 链接：http://oj.daimayuan.top/ 演示视频请戳我 推荐测试链接：http://oj.daimayuan.top/problem/148 @高山 @高山
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 （我很着急，人去哪儿了？）
哈哈哈哈哈哈哈哈哈哈哈~ sorry，在审核，不知触发了什么敏感关键词.... 说明一下，题目转载于代码源
页:
[1]