推箱子1～15关图解求解

来源：蜘蛛抓取(WebSpider) 时间：2024-02-14 12:00 标签： 推箱子1～15关图解
一个推箱子游戏自动求解Delphi小程序，可以从剪切板粘贴关卡XSB到编辑区域，也可以手动输入：
# : 墙壁
- : 地板
.
: 目标点
$ : 箱子
* :
目标点上的箱子
@: 人
+ : 目标点上的人
推箱子求解器
2018-12-04 上传
大小：208KB
题目描述：大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。输入描述：每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述：输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
示例：输入例子1:
4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...
输出例子1:
3
11
解析：BFS很经典的一题，即为找单一最短路径，利用队列（用队列来保存未访问的结点，先进先出）实现的搜索算法。利用队列，把当前位置可移动的格子压入进去，其中可移动的格子为：人的下一步不超出墙外；人的下一步不为障碍物；若人的下一步为箱子，则箱子的移动方向应该跟人同向，且：箱子的下一步不超出墙外；箱子的下一步不为障碍物；此外，人在移动箱子是可以踩未移动箱子前的格子的，因此，判断一个格子是否被重复踩踏应该根据人的位置和箱子的共同状态决定。#include <iostream>
#include <queue>
using namespace std;
int N, M;
//地图大小
char map[10][10];
//地图，防止越界
//查看当前格子是否已被踩，格式为<人当前格子，盒子当前格子>
int map_flag[10][10][10][10];
//四个方向选择
int choose[4][2] = { -1,0,1,0,0,-1,0,1 };
//建立节点
struct Point
{
//人的位置
int people_x, people_y;
//箱子位置
int box_x, box_y;
//到达该格子的步数
int count;
Point(int people_x,int people_y,int box_x,int box_y):
people_x(people_x),people_y(people_y),box_x(box_x),box_y(box_y),count(0)
{
}
};
int BFS(int people_x,int people_y,int box_x,int box_y)
{
//建立路径队列
queue<Point> visit_queue;
//先把当前位置压入
visit_queue.push(Point(people_x, people_y, box_x, box_y));
while (!visit_queue.empty())
{
//访问、弹出、标记当前节点
Point now_Point = visit_queue.front();
visit_queue.pop();
map_flag[now_Point.people_x][now_Point.people_y][now_Point.box_x][now_Point.box_y] = 1;
//若箱子到达终点，返回步数
if(map[now_Point.box_x][now_Point.box_y]=='@')
{
return now_Point.count;
}
//若不是，则对四个方向进行分析
for(int i=0;i<4;i++)
{
//准备判断的格子
Point next_Point = now_Point;
next_Point.people_x += choose[i][0];
next_Point.people_y += choose[i][1];
next_Point.count++;
//分析下一个格子是否出界或撞墙
if(next_Point.people_x<1
next_Point.people_x>N
next_Point.people_y<1
next_Point.people_y>M
map[next_Point.people_x][next_Point.people_y]=='#')
{
continue;
}
//如果踩到的是箱子，则箱子按同方向前进一格
if(next_Point.people_x==next_Point.box_x&&
next_Point.people_y==next_Point.box_y)
{
next_Point.box_x += choose[i][0];
next_Point.box_y += choose[i][1];
//判断箱子是否出界或撞墙
if(next_Point.box_x<1
next_Point.box_x>N
next_Point.box_y<1
next_Point.box_y>M
map[next_Point.box_x][next_Point.box_y]=='#')
{
continue;
}
}
//若当前格子没有踩过，则压入该状态
if(map_flag[next_Point.people_x][next_Point.people_y][next_Point.box_x][next_Point.box_y]!=1)
{
visit_queue.push(next_Point);
}
}
}
//若队列已经遍历空且没有返回，说明无法完成游戏
return -1;
}
int main()
{
cin >> N >> M;
int people_x, people_y;
int box_x, box_y;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
cin >> map[i][j];
if(map[i][j]=='X')
{
people_x = i;
people_y = j;
}
else if(map[i][j] == '*')
{
box_x = i;
box_y = j;
}
}
}
cout << BFS(people_x, people_y, box_x, box_y) << endl;
}

我要回帖

更多关于 推箱子1～15关图解 的文章

 

随机推荐