大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个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<stdio.h>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
struct state
{
int px, py; //玩家坐标
int bx, by; //箱子坐标
int step;
state(int x, int y, int s, int t) : px(x), py(y), bx(s), by(t), step(0) {}
state update(int dx, int dy, vector<vector<char>>& Map)
{
state s(px + dx, py + dy, bx, by);
s.step = this->step + 1;
//如果玩家位置与箱子位置重合，更新箱子位置
if (s.px == s.bx && s.py == s.by)
{
s.bx += dx;
s.by += dy;
}
int n = Map.size(), m = Map[0].size();
if (s.px < 0 || s.px >= n || s.py < 0 || s.py >= m || s.bx < 0 || s.bx >= n || s.by < 0 || s.by >= m)
{
s.step = -1;
return s;
}
if (Map[s.bx][s.by] == '#' || Map[s.px][s.py] == '#')
{//撞墙
s.step = -1;
}
return s;
}
};
int* setMap(vector<vector<char>>& Map, int n, int m)
{
int *index = new int[6];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> Map[i][j];
switch (Map[i][j])
{
case 'X':
index[0] = i;
index[1] = j;
break;
case '*':
index[2] = i;
index[3] = j;
break;
case '@':
index[4] = i;
index[5] = j;
break;
}
}
}
return index;
}
void debug(vector<vector<char>>& Map)
{
int n = Map.size(), m = Map[0].size();
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
cout << Map[i][j] << " ";
cout << endl;
}
}
int main()
{
const int wx[4] = { 0, 1, 0, -1 };
const int wy[4] = { 1, 0, -1, 0 };
int n, m;
cin >> n >> m;
vector<vector<char>> Map(n, vector<char>(m, 0));
int *where = setMap(Map, n, m); //存储初始玩家、初始箱子、终点位置
//状态数组
bool flag[10][10][10][10]; //true表示可访问
//这里使用memset笔试的编译器会报错，可以使用4层vector初始化
memset(flag, true, sizeof(flag));
queue<state> que;
//初始化数据
flag[where[0]][where[1]][where[2]][where[3]] = false;
que.push(state(where[0], where[1], where[2], where[3]));
//bfs
while (!que.empty())
{//取出一个状态
state s = que.front();
que.pop();
//该状态是否是终态
if (s.bx == where[4] && s.by == where[5])
{
cout << s.step << endl;
delete[] where;
system("pause");
return 0;
}
//向四个方向移动
for (int i = 0; i < 4; ++i)
{
state ns = s.update(wx[i], wy[i], Map);
if (ns.step != -1 && flag[ns.px][ns.py][ns.bx][ns.by])
{
flag[ns.px][ns.py][ns.bx][ns.by] = false;
que.push(ns);
}
}
}
cout << -1 << endl;
delete[] where;
system("pause");
return 0;
}