时间限制：1秒
空间限制：32768K
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述:
每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子:
4 4
....
..*@
....
.X..
输出例子:
3
11
#include<iostream>
#include<queue>
#include<memory.h>
#include<string>
using namespace std;
static pair<
int,
int>
operator+(
const pair<
int,
int> &lhs,
const pair<
int,
int> &rhs)
{
pair<
int,
int> p;
p.first = lhs.first + rhs.first;
p.second = lhs.second + rhs.second;
return p;
}
class Game
{
using point = pair<
int,
int>;
using step =
int[
11][
11][
11][
11];
using state =
struct State
{
point player;
point box;
State(point p, point b):player(p), box(b){}
};
point direction[
4] = {point(
1,
0),point(-
1,
0),point(
0,
1),point(
0,-
1)};
point player;
point box;
point dest;
vector<vector<char>> map;
step stepUsed;
public:
Game();
void init();
int search();
private:
bool inBoundary(
const point &p)
const
{
bool in = (p.first >=
0 && p.first <
map.size() && p.second >=
0 && p.second <
map[
0].size());
if(in)
return in && (
map[p.first][p.second] !=
'#');
else
return false;
}
int getStep(
const point &p,
const point &b)
const
{
return stepUsed[p.first][p.second][b.first][b.second];
}
void setStep(
const point &p,
const point &b,
int s)
{
stepUsed[p.first][p.second][b.first][b.second] = s;
}
};
Game::Game()
{
int x, y;
cin >> x >> y;
map =
vector<vector<char>>(x,
vector<char>(y));
for (size_t i =
0; i <
map.size(); ++i)
{
for (size_t j =
0; j <
map[
0].size(); ++j)
{
cin >>
map[i][j];
}
}
init();
}
void Game::init()
{
for (size_t i =
0; i <
map.size(); ++i)
{
for (size_t j =
0; j <
map[i].size(); ++j)
{
if (
map[i][j] ==
'@')
{
dest.first = i;
dest.second = j;
}
if (
map[i][j] ==
'X')
{
player.first = i;
player.second = j;
}
if (
map[i][j] ==
'*')
{
box.first = i;
box.second = j;
}
}
}
memset(&stepUsed,
0,
sizeof(step));
}
int Game::search()
{
queue<state> q;
q.push(state(player, box));
setStep(player, box,
1);
while (!q.empty())
{
state c = q.front();
q.pop();
player = c.player;
box = c.box;
if (box == dest)
return getStep(player, box) -
1;
for (
int i =
0; i <
4; ++i)
{
point nextPlayer = player + direction[i];
if (!inBoundary(nextPlayer))
continue;
if (nextPlayer == box)
{
point nextBox = box + direction[i];
if (!inBoundary(nextBox))
continue;
if (getStep(nextPlayer, nextBox) !=
0)
continue;
setStep(nextPlayer, nextBox, getStep(player, box) +
1);
q.push(state(nextPlayer, nextBox));
}
else
{
if (getStep(nextPlayer, box) !=
0)
continue;
setStep(nextPlayer, box, getStep(player, box) +
1);
q.push(state(nextPlayer, box));
}
}
}
return -
1;
}
int main()
{
Game g;
cout << g.search();
return 0;
}
