|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-1-8 21:47 编辑
大家好，今天是每周一练的第7期
这次的每周一练由我帮助用户@高山 发帖
题目名称：推箱子
[注，因周六周日上学原因，所以我提前发]
这道题可能有点难度，大概是CSP-J第三题的难度，大家听不懂没有关系！
题目说明：
wls 在玩一个经典的推箱子小游戏，他需要控制一个角色将箱子从起始位置推到终点。
游戏在一个 n×m 的网格图中进行，网格图中存在空地和障碍物，整张地图被一圈（环绕在地图外的）障碍物包围。
地图由 n×m 个字符组成，其中：
P 表示角色的初始位置；
B 表示箱子的初始位置；
E 表示箱子的终点；
. 表示空地；
# 表示障碍物。
角色的初始位置、箱子的初始位置和终点均视为空地。
角色每次只能朝上下左右四个方向移动一格。
当角色和箱子相邻时可以尝试推箱子。假如角色在箱子的左边，箱子只能往右推。假如角色在箱子的右边，箱子只能往左推。假如角色在箱子的上边，箱子只能往下推。假如角色在箱子的下边，箱子只能往上推。当箱子的推动方向的那一格不是障碍物的时候，角色和箱子会一起向目标方向移动一格。
例如下图，P 表示角色，B 表示箱子:人向右推一格箱子后，会变成：注意：在任何时刻，角色和箱子不可以出现在同一个位置上；角色和箱子都不能移动到障碍物上；角色和箱子不能移动到地图外；角色只能往箱子方向推箱子但不能拉箱子。
现在 wls 想请你计算出最少需要移动多少步可以将箱子送到目的地，注意人的单独移动和一次推箱子的移动均算作一步。如果不可能完成任务，输出 -1。
输入说明：
第一行两个整数 n,m 表示地图的行数和列数。
接下来 n 行，每行一个长度为 m 的字符串，详细含义见题目描述。
输出说明：
输出一行一个数，表示最小移动步数。如果不可能完成任务，输出 -1。
样例输入1样例输出1
样例输入输出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，就能得分啦！
大概是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[61 * 61 * 61 * 61 + 1];
int step[61][61][61][61];
int n, m, e_x, e_y, p_x, p_y, b_x, b_y, front = 1, rear = 0;
char map[61][62];
const int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
#define check_pos(x, y) (x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#')
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[i] + 1);
for (int j = 1; j <= m; ++j)
if (map[i][j] == 'E') e_x = i, e_y = j;
else if (map[i][j] == 'P') p_x = i, p_y = j;
else if (map[i][j] == 'B') b_x = i, b_y = j;
}
bfs();
}
Step 4.0:
bfs函数基本框架：void bfs() {
queue[++rear] = {p_x, p_y, b_x, b_y};
step[p_x][p_y][b_x][b_y] = 0;
while (rear + 1 != front) {
//...
}
printf("-1");
}
Step 4.1:
获取队首位置，并判断：int fpx = queue[front].pla_x, fpy = queue[front].pla_y, fbx = queue[front].box_x, fby = queue[front].box_y;
if (fbx == e_x && fby == e_y) {
printf("%d", step[fpx][fpy][fbx][fby]);
exit(0);
}
++front;
Step 4.2:
得到新坐标，并判断是否该加入队列（重点，也是难点）：
Step 4.2.1:
得到新坐标：for (int i = 0; i < 4; ++i) {
int npx = fpx + dir[i][0], npy = fpy + dir[i][1];
int nbx = fbx + dir[i][0], nby = fby + dir[i][1];
}
因为后面箱子可能要移动，所以我也定义了nbx,nby
Step 4.2.2:
当玩家坐标与原本的箱子坐标重合：
表示玩家移动了箱子：if (npx == fbx && npy == fby) {
if (check_pos(npx, npy) && check_pos(nbx, nby) && step[npx][npy][nbx][nby] == -1) {
step[npx][npy][nbx][nby] = step[fpx][fpy][fbx][fby] + 1;
queue[++rear] = {npx, npy, nbx, nby};
}
}
Step 4.2.3:
否则直接加入： else {
if (check_pos(npx, npy) && step[npx][npy][fbx][fby] == -1) {
step[npx][npy][fbx][fby] = step[fpx][fpy][fbx][fby] + 1;
queue[++rear] = {npx, npy, fbx, fby};
}
}
至此，我们的代码完成啦！
完整参考代码#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
struct Data {
int pla_x, pla_y, box_x, box_y;
}queue[61 * 61 * 61 * 61 + 1];
int step[61][61][61][61];
int n, m, e_x, e_y, p_x, p_y, b_x, b_y, front = 1, rear = 0;
char map[61][62];
const int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
#define check_pos(x, y) (x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#')
void bfs() {
queue[++rear] = {p_x, p_y, b_x, b_y};
step[p_x][p_y][b_x][b_y] = 0;
while (rear + 1 != front) {
int fpx = queue[front].pla_x, fpy = queue[front].pla_y, fbx = queue[front].box_x, fby = queue[front].box_y;
if (fbx == e_x && fby == e_y) {
printf("%d", step[fpx][fpy][fbx][fby]);
exit(0);
}
++front;
for (int i = 0; i < 4; ++i) {
int npx = fpx + dir[i][0], npy = fpy + dir[i][1];
int nbx = fbx + dir[i][0], nby = fby + dir[i][1];
if (npx == fbx && npy == fby) {
if (check_pos(npx, npy) && check_pos(nbx, nby) && step[npx][npy][nbx][nby] == -1) {
step[npx][npy][nbx][nby] = step[fpx][fpy][fbx][fby] + 1;
queue[++rear] = {npx, npy, nbx, nby};
}
} else {
if (check_pos(npx, npy) && step[npx][npy][fbx][fby] == -1) {
step[npx][npy][fbx][fby] = step[fpx][fpy][fbx][fby] + 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[i] + 1);
for (int j = 1; j <= m; ++j)
if (map[i][j] == 'E') e_x = i, e_y = j;
else if (map[i][j] == 'P') p_x = i, p_y = j;
else if (map[i][j] == 'B') b_x = i, b_y = j;
}
bfs();
return 0;
}
创作不易，求评分
上一篇：bfs练习2
下一篇 摘苹果
说明：题目来源于 代码源 ： 链接：http://oj.daimayuan.top/ |
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-10-7 13:53:24
置顶卡
千斤顶
显身卡
发表于 2022-10-7 18:14:19
楼主
发表于 2022-10-7 14:30:40
非常好！希望创作出更多期
