大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上,有1个玩家、1个箱子、1个目的地以及若干障碍,其余是空地。玩家可以往上下左右4个方向移动,但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子,箱子也会按这个方向移动一格,当然,箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后,游戏目标达成。现在告诉你游戏开始是初始的地图布局,请你求出玩家最少需要移动多少步才能够将游戏目标达成。
**输入描述**:
每个测试输入包含
1个测试用例
第一行输入两个数字
N,M表示地图的大小。其中
0<
N,M<=
8。
接下来有
N行,每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含
1个玩家、
1个箱子、
1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候,输出-1。
例子
4 4
....
..*@
....
.X..
输出结果:3
6 6
...
......
..
..X...
.@
输出结果为
11
下面是代码,有详细注解,核心是队列的数据结构和BFS搜索 程序在VS2015下编译通过。
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int state[
10][
10][
10][
10];
struct q
{
int px, py, bx, by;
q(
int x,
int y,
int bx,
int by) :px(x), py(y), bx(bx), by(by) {}
};
int moves[
4][
2] = { {
0,
1},{
0,-
1},{-
1,
0},{
1,
0} };
char map[
10][
10];
int chx, chy, cbx, cby, ex, ey, n, m;
bool bound(
int x,
int y)
{
if (x <
0 || y <
0 || x >= n || y >= m ||
map[x][y] ==
'#')
return true;
else
return false;
}
int bfs()
{
state[chx][chy][cbx][cby] =
1;
q temp(chx, chy, cbx, cby);
queue<q> que;
que.push(temp);
while (que.size())
{
temp = que.front();
que.pop();
if (temp.bx == ex&&temp.by == ey)
return state[temp.px][temp.py][temp.bx][temp.by]-
1;
for (
int i =
0; i <
4; i++)
{
int px = temp.px + moves[i][
0];
int py = temp.py + moves[i][
1];
if (bound(px, py))
continue;
if (px == temp.bx&&py == temp.by)
{
if (bound(temp.bx + moves[i][
0], temp.by + moves[i][
1]))
continue;
state[px][py][temp.bx + moves[i][
0]][temp.by + moves[i][
1]] =
state[temp.px][temp.py][temp.bx][temp.by] +
1;
que.push(q(px, py, temp.bx + moves[i][
0], temp.by + moves[i][
1]));
}
else
{
if (state[px][py][temp.bx][temp.by])
continue;
state[px][py][temp.bx][temp.by] = state[temp.px][temp.py][temp.bx][temp.by] +
1;
que.push(q(px, py, temp.bx, temp.by));
}
}
}
return -
1;
}
int main()
{
cin >> n >> m;
for (
int i =
0; i < n; i++)
{
scanf_s(
"%s",
map[i],m+
1);
}
for (
int i =
0; i < n; i++)
{
for (
int j =
0; j < m; j++)
{
if (
map[i][j]==
'*')
{
cbx = i;
cby = j;
}
else if (
map[i][j] ==
'X')
{
chx = i;
chy = j;
}
else if (
map[i][j] ==
'@')
{
ex = i;
ey = j;
}
}
}
cout << bfs() << endl;
return 0;
}
题目来自牛客网,若侵权,则请联系我,我将删除
转载请注明原文地址: https://ju.6miu.com/read-4556.html