题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1254
题目分析：
做这道题，感觉挺简单的，做着做着就错了20次， 我也是醉了， WA到吐的节奏啊！
思路：
1.标记人的位置 和 箱子的位置两个动态坐标 来判断是否这个状态出现过， 但是有一点要， 虽然人和箱子同时出现了重复状态 但是还有一个状态需要考虑，就是推箱子的步数，
虽然到达了同样的地点但是，步数不一样也是不一样的状态。下面会有个数据可以观察一下。
2.结构体里保存 人的坐标， 箱子的坐标， 推箱子的步数
3（1）.每次人走一步，判断这一步是否合法， 然后判断人是否与箱子重合， 如果与箱子重合了， 则箱子再向前一步，判断箱子的状态是否合法！如果合法加入队列。
（2）如果箱子和人不重合，并且人和箱子的状态合法！则加入队列。
下面是代码：
#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define maxn 10
#define INF 0xfffffff
#define min(a,b) (a<b?a:b)
struct Point
{
int x, y;//人的坐标
int nx, ny;//箱子的坐标
int step;
} Ps;
int dir[][] = { {,},{,-},{-,},{,} };
int maps[maxn][maxn];
int vis[maxn][maxn][maxn][maxn];//人的坐标，，，箱子的坐标
int m, n; bool OK(Point P)
{
return P.x >= && P.x < m && P.y >= && P.y < n && maps[P.x][P.y] != && P.step < vis[P.x][P.y][P.nx][P.ny];
} bool OK2(Point P)
{
return P.nx >= && P.nx < m && P.ny >= && P.ny < n && maps[P.nx][P.ny] != && P.step < vis[P.x][P.y][P.nx][P.ny];
}
void init()
{
for(int i=; i<maxn; i++)
for(int j=; j<maxn; j++)
for(int k=; k<maxn; k++)
for(int p=; p<maxn; p++)
vis[i][j][k][p] = INF;
}
int BFS()
{
Point P, Pn;
queue<Point> Q;
Q.push(Ps);
int ans = INF; vis[Ps.x][Ps.y][Ps.nx][Ps.ny] = true; while( !Q.empty() )
{
P = Q.front();
Q.pop(); if(maps[P.nx][P.ny] == )
{
ans = min(ans,P.step);
} for(int i=; i<; i++)
{
Pn = P;//人向前走一步
Pn.x += dir[i][];
Pn.y += dir[i][];
if( OK(Pn) )//判断人走一步是否合法
{
if( Pn.x == Pn.nx && Pn.y == Pn.ny)//如果人和箱子重合则箱子向前进一步
{
Pn.nx += dir[i][];
Pn.ny += dir[i][];
Pn.step ++;
if( OK2(Pn))//判断箱子前进是否合法
{
vis[Pn.x][Pn.y][Pn.nx][Pn.ny] = Pn.step;
Q.push(Pn);
}
}
else
{
vis[Pn.x][Pn.y][Pn.nx][Pn.ny] = Pn.step;
Q.push(Pn);
}
}
}
}
return ans;
} int main()
{
int T, k;
scanf("%d",&T); while(T--)
{
init();//对VIS进行初始化 scanf("%d%d",&m,&n); for(int i=; i<m; i++)
{
for(int j=; j<n; j++)
{
scanf("%d",&maps[i][j]);
if(maps[i][j] == )
Ps.x = i, Ps.y = j, Ps.step = ;
else if(maps[i][j] == )
Ps.nx = i, Ps.ny = j;
}
}
k = BFS();
if(k == INF)
k = -;
printf("%d\n", k);
}
return ;
}