|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
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] != '#')
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[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全部为-1，接着读入n,m和整个地图，然后遍历这一行的字符串，如果为E,P,B，更新对应的坐标
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");
- }
先把基本数据加入队列（不知道有没有表达清楚），再设置步数，接着在队列非空的情况下执行，如果队列空了也没找到解，说明无解，输出-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];
- }
说明：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[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};
- }
- }
更简单，只需要判断一个坐标即可，因为箱子坐标不变，所以用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
非常好！希望创作出更多期
