【C++板块提升计划】每周一练第七期推箱子【代码含注释讲解】,C\C++交流,技术交流,鱼C论坛

zhangjinxuan 发表于 2022-10-7 13:53:24

【C++板块提升计划】每周一练第七期推箱子【代码含注释讲解】

本帖最后由 zhangjinxuan 于 2023-1-8 21:47 编辑

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

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

题目名称：推箱子

[注，因周六周日上学原因，所以我提前发]

这道题可能有点难度，大概是CSP-J第三题的难度，大家听不懂没有关系！

题目说明：
wls 在玩一个经典的推箱子小游戏，他需要控制一个角色将箱子从起始位置推到终点。

游戏在一个 n×m 的网格图中进行，网格图中存在空地和障碍物，整张地图被一圈（环绕在地图外的）障碍物包围。

地图由 n×m 个字符组成，其中：

P 表示角色的初始位置；

B 表示箱子的初始位置；

E 表示箱子的终点；

. 表示空地；

# 表示障碍物。

角色的初始位置、箱子的初始位置和终点均视为空地。

角色每次只能朝上下左右四个方向移动一格。

当角色和箱子相邻时可以尝试推箱子。假如角色在箱子的左边，箱子只能往右推。假如角色在箱子的右边，箱子只能往左推。假如角色在箱子的上边，箱子只能往下推。假如角色在箱子的下边，箱子只能往上推。当箱子的推动方向的那一格不是障碍物的时候，角色和箱子会一起向目标方向移动一格。

例如下图，P 表示角色，B 表示箱子:
####
.PB.
####
人向右推一格箱子后，会变成：
####
..PB
####
注意：在任何时刻，角色和箱子不可以出现在同一个位置上；角色和箱子都不能移动到障碍物上；角色和箱子不能移动到地图外；角色只能往箱子方向推箱子但不能拉箱子。

现在 wls 想请你计算出最少需要移动多少步可以将箱子送到目的地，注意人的单独移动和一次推箱子的移动均算作一步。如果不可能完成任务，输出 -1。

输入说明：
第一行两个整数 n,m 表示地图的行数和列数。

接下来 n 行，每行一个长度为 m 的字符串，详细含义见题目描述。

输出说明：
输出一行一个数，表示最小移动步数。如果不可能完成任务，输出 -1。

样例输入1
3 4
P...
..B.
.E.#
样例输出1
8

样例输入输出2
详见测试链接

样例解释1
角色先从 (1,1) 移动到 (2,4)，将箱子推动到 (2,2)，角色再从 (2,3) 移动到 (1,2)，将箱子推到终点。

数据规模
对于 20% 的数据，满足 n=1。

对于另外 20% 的数据，满足角色最少移动的步数 ≤15。

对于另外 20% 的数据，保证地图中没有障碍物，并且角色的初始位置、箱子的初始位置和终点均不在地图的边界上。

对于 100% 的数据，满足 3≤n,m≤60，数据保证角色的初始位置、箱子的初始位置和终点唯一。

测试链接
评论区发布

空间，时间限制
时间限制:1 s空间限制:1024 MB

这一期我不想只给大家公布代码了，这一次我想一步一步的教大家解题！

讲解

Step -1

我们输出-1，就能得分啦！{:5_109:}

大概是10分的样子吧....

爬！这点分数要求太低！我要100，我要100！

好的，现在进入正题：
Step 0.0:
想思路，这道题肯定是一道搜索题，唯二有用的搜索只有BFS和DFS

Step 0.1:
时间复杂度分析：
如果使用DFS，那么时间复杂度肯定很高，大概是O(4^(nm))！

不用想了....DFS肯定不行，只能得20分....

但是如果使用BFS，时间复杂度就应该是O（(nm)^2)，为什么呢？

因为全场唯一可移动的，只有箱子和玩家，箱子的位置最多有nm种，玩家的位置也是最多nm-1种，所以游戏所有状态最多约是nm^2

因为BFS最坏情形就是每一种状态都遍历，所以时间复杂度是O((nm)^2)，这一定可以过，冲冲冲！我们来写代码！

Step 1:
基本框架：
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int main() {
return 0;
}

Step 2:
变量定义：
struct Data {
int pla_x, pla_y, box_x, box_y;
}queue;
int step;

int n, m, e_x, e_y, p_x, p_y, b_x, b_y, front = 1, rear = 0;
char map;
const int dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
#define check_pos(x, y) (x >= 1 && x <= n && y >= 1 && y <= m && map != '#')
data表示当前的数据，因为全场可移动的只有玩家，箱子，我们只用记玩家，箱子的坐标即可

queue是BFS所用的队列，其实我觉得不用61 ^ 4 + 1,60 ^ 4 + 1就行了（我是1...base)

step_i_j_k_l表示玩家坐标在i,j的位置，箱子位置在k,l的位置时，所需的步数

n,m表示大小，e_x,e_y,p_x,p_y,b_x,b_y表示盒子终点坐标，玩家当前坐标，盒子当前坐标

front,rear不讲......

map表示整个地图长什么样，dir表示4个方向，而check_pos表示当前坐标是否合法

Step 3:
main函数：
int main() {
memset(step, 255, sizeof(step));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", map + 1);
for (int j = 1; j <= m; ++j)
if (map == 'E') e_x = i, e_y = j;
else if (map == 'P') p_x = i, p_y = j;
else if (map == 'B') b_x = i, b_y = j;
}
bfs();
}
一开始，初始化step全部为-1，接着读入n,m和整个地图，然后遍历这一行的字符串，如果为E,P,B，更新对应的坐标

Step 4.0:
bfs函数基本框架：
void bfs() {
queue[++rear] = {p_x, p_y, b_x, b_y};
step = 0;
while (rear + 1 != front) {
//...
}
printf("-1");
}
先把基本数据加入队列（不知道有没有表达清楚），再设置步数，接着在队列非空的情况下执行，如果队列空了也没找到解，说明无解，输出-1

Step 4.1:
获取队首位置，并判断：
int fpx = queue.pla_x, fpy = queue.pla_y, fbx = queue.box_x, fby = queue.box_y;
if (fbx == e_x && fby == e_y) {
printf("%d", step);
exit(0);
}
++front;
先获取队首的数据，再判断箱子是否到达指定坐标，到达输出步数，并推出，然后队首弹出

Step 4.2:
得到新坐标，并判断是否该加入队列（重点，也是难点）：

Step 4.2.1:
得到新坐标：
for (int i = 0; i < 4; ++i) {
int npx = fpx + dir, npy = fpy + dir;
int nbx = fbx + dir, nby = fby + dir;
}
说明：npx 表示 new player x (新的玩家x坐标），剩下的自己想

因为后面箱子可能要移动，所以我也定义了nbx,nby

Step 4.2.2:
当玩家坐标与原本的箱子坐标重合：
表示玩家移动了箱子：
if (npx == fbx && npy == fby) {
if (check_pos(npx, npy) && check_pos(nbx, nby) && step == -1) {
step = step + 1;
queue[++rear] = {npx, npy, nbx, nby};
}
}
第一行代码判断是否重合，重合的话就判断两个坐标是否合法（重合的话也代表箱子也将要移到新的坐标），再判断是否被访问过，都满足就加入队列并更新答案

Step 4.2.3:
否则直接加入：
else {
if (check_pos(npx, npy) && step == -1) {
step = step + 1;
queue[++rear] = {npx, npy, fbx, fby};
}
}
更简单，只需要判断一个坐标即可，因为箱子坐标不变，所以用fbx,fby

至此，我们的代码完成啦！{:10_298:}

完整参考代码
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

struct Data {
int pla_x, pla_y, box_x, box_y;
}queue;
int step;

int n, m, e_x, e_y, p_x, p_y, b_x, b_y, front = 1, rear = 0;
char map;
const int dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
#define check_pos(x, y) (x >= 1 && x <= n && y >= 1 && y <= m && map != '#')

void bfs() {
queue[++rear] = {p_x, p_y, b_x, b_y};
step = 0;
while (rear + 1 != front) {
int fpx = queue.pla_x, fpy = queue.pla_y, fbx = queue.box_x, fby = queue.box_y;
if (fbx == e_x && fby == e_y) {
printf("%d", step);
exit(0);
}
++front;
for (int i = 0; i < 4; ++i) {
int npx = fpx + dir, npy = fpy + dir;
int nbx = fbx + dir, nby = fby + dir;
if (npx == fbx && npy == fby) {
if (check_pos(npx, npy) && check_pos(nbx, nby) && step == -1) {
step = step + 1;
queue[++rear] = {npx, npy, nbx, nby};
}
} else {
if (check_pos(npx, npy) && step == -1) {
step = step + 1;
queue[++rear] = {npx, npy, fbx, fby};
}
}
}
}
printf("-1");
}

int main() {
memset(step, 255, sizeof(step));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", map + 1);
for (int j = 1; j <= m; ++j)
if (map == 'E') e_x = i, e_y = j;
else if (map == 'P') p_x = i, p_y = j;
else if (map == 'B') b_x = i, b_y = j;
}
bfs();
return 0;
}

创作不易，求评分{:10_254:}

上一篇：bfs练习2
下一篇摘苹果

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

高山发表于 2022-10-7 18:14:19

zhangjinxuan 发表于 2022-10-7 13:59
样例输入2：

样例输出2：

演示视频请戳我

zhangjinxuan 发表于 2022-10-7 13:54:27

@hveagle @元豪 @不二如是求支持{:10_254:}

hveagle 发表于 2022-10-7 13:55:25

{:7_146:}

zhangjinxuan 发表于 2022-10-7 13:57:24

因为测试链接可能无法公开，所以大家可以把自己写的代码发给我，我来帮你测

zhangjinxuan 发表于 2022-10-7 13:59:01

样例输入2：
60 60
.......#....#..#.#....#...#.#.###..#........###.......#..##.
#..###.##......#..#.....#..................#....#.#.#.#.....
.#####..##.##.#..##.#..#.##.##...#..........#..#..#.#....#..
.#...#...##..###.##.##.#...#.#....##......##..####.#..#.#.#.
.#......##..#.........#...#....##....##..........#.#..#.....
..#...##.......#.....#..###.#....#.......#.........##...#...
.##..###.E....#.##..#..#..#...#...#.##........#.#.....#.#.#.
...#..................#....#....#..###........#.....#.##...#
.#..##.#........#.......#...#..#.###.#..##.......#......#...
......#...........#..........#....#......##.....#.#.....#..#
.#......#..#...#.#.....#.........#........#.#..#.#...###.##.
##...#....#.#....###..#.#.......#..#.....##.....#.#..##...#.
.#.#.#.#..##......#..#..#....##.#......#..........#....#...#
...#.....#.....#...#.##.....#....#####.....##..#..##.#..#...
#.##.#...##.###..#...##..#..#.#..###...#.#..#.#....#..#..#..
#.#.....##...#......####.#.#.......#.....####..#..#.....###.
.##......###.....#.##..#.....#.#.....#....#.....#..#.#...##.
.#.....#.......#.#........#.#.#.#...#...#.......#.....#.####
.......#.##.#......#.#.#.........#....#..............#...##.
..#...#.#..#.#.#............#.....#.#......#.##.#...#....##.
#........#..#....#....##.....#.................#..#.#....#..
#....##.#......###.#...#..#..#.#.#...####..#........#....#..
....#.#.##.....#....####.#...##.#.##...##......###.....#....
##.............###....#...#.#######....##..#..#.##.#.......#
....#..#.##..#.#...#...........#....##........#..........#..
....#.#....#.#.##.##...#.##..#....#....##......#...#...####.
..........#..#..#......#.##.#.#..##..#....#...##P....#.##...
....#.#.#...#..#..#....#........#..#...#......#.....#..#.#.#
..#.#..#......#.#.#.#..#....##.....#...#...#.#.#.#...##.....
.#.##..#.....#...#.##..#.#...#.........##..#....#.##....##..
..##..#..#..........#..#....#.##.#...#.#.....#.##..#....#...
#.##..#.........#..###.#.#........#...##..#....##.#...###..#
.....#....##.#.##.####..............#...........#.#..#....##
#...#...##.#......######..#..##.....#......##....##..#...#.#
#####..###..........#.##...#....##.....#..##..##..#.#..#..#.
.##..#........##.#.........#..##.#.....###.....#........#.##
.#.#...........#........#.....##....####..#......B...#.#...#
#.#......#.....#......#....#...##.###.##...#.........#......
..#.##.#.#.#..#....#.......#..#...#.##...#......##..##.....#
...##.###....##..........#.......###.#..........##.###.#....
.#.....#.#.####..#.......#....#......###.#....###.###...#.#.
.......##..###...#.##.#...#.##..#.###...#.......#.#....##...
##.#..#.#.###.#.#..#.#.#.##...#.#.......#.....#.##.....#...#
#....#..#......#....#..##.......#........#...#....#...#...#.
..#..#.##....#.###...#.#.#.##...........#.##.#..##.....#..#.
.....#........##.###...#.##..............#..#.....#..#......
.....#....#.........#.##..#.###...#............#......#.....
#...#.#...##....#..............#..................#.........
#.##...##...#....#.....#..#..###.#....#.....##.........#...#
...#............###..#.#...###......###.............#.#.....
..#.#...##...##.##........##....#..#.......#..#..........#.#
#.#..##..##..##.###...#...###.......#........###.#....#..#.#
.#.###.....#..#..###.....#........#...#...#.#..#..#.........
........#...........#.#.#.##..#..##....#.....#..#####..#....
.##.....#.##...#..#........#..#.......................#..#.#
#..##.#....###...#.#.....#.#...#....##.....#....#..##.......
...#.#......#...##..##..#......##.#.#...###..#....#.......##
.#.####....##..#.#..........#####.....#...#....##.##.......#
...###......#.#..#..##....#.#....##.....#.#.........#...#...
......#####.##.........#..#...##..#.#...#..#....#...........

样例输出2：
126

不二如是 发表于 2022-10-7 14:30:40

{:10_275:}非常好！希望创作出更多期

柿子饼同学 发表于 2022-10-7 14:45:09

本帖最后由柿子饼同学于 2022-10-7 14:46 编辑

stl queue : qwq
return 0; : qwq
{:7_146:}

陈尚涵 发表于 2022-10-7 16:11:45

这题可以的，不止t3，应该是t3-t4

zhangjinxuan 发表于 2022-10-7 16:54:48

陈尚涵发表于 2022-10-7 16:11
这题可以的，不止t3，应该是t3-t4

感谢支持{:10_256:}

.yun. 发表于 2022-10-11 19:05:56

{:5_91:}

页: [1]

鱼C论坛's Archiver

【C++板块提升计划】每周一练第七期 推箱子【代码含注释讲解】

【C++板块提升计划】每周一练第七期推箱子【代码含注释讲解】