就我的理解来说这个题，本质上是一个DP题，不应该说是搜索，因为我的做法是把表格中所有的数据都找到，使用队列暴力来遍历出所有状态，因为题目中的数据范围小，所有耗时也小。
首先分析箱子是一个被动物体，人是主动物体，箱子的移动取决于人的移动，所以在bfs中只需要让人去移动，进而带动箱子就可以了。我们使用dp[x1][y1][x2][y2]来记录状态，分别代表人和箱子的位置。在队列实现DP的过程中，我们必须要把当前所在的情况标记为未走过，这个很重要。有人可能会质疑，这样可能导致无限的入队列，导致死循环，所以需要一个技巧，首先新的状态是否更新跟这个状态是否被标记无关，所以能否让这个点入队列，需要首先满足状态值得更新的条件，所以我们不可能去走无意义的回头路，不可能会产生走过来走过去，从而导致死循环的情况。然后就要满足这个点未被标记的情况，才能入队列，标记这个点。
当然有人也会问，只要把状态更新了就可以了，干嘛非要入队列呢？如果不仅队列，更新的仅仅是这个状态，其他的状态无法经过他转移，无法获得最优子结构，就不符合DP的思想，就是错误的了。（当然这个地方可能也仅仅是我不懂，但是这个标记方法还是很重要的），我给出一个例子吧。
0 0 0 0 0 0
0 0 1 1 1 0
0 0 1 4 0 0
0 0 1 2 1 0
0 0 0 0 3 0
0 0 0 0 1 0
0 0 0 0 0 0
我相信你很快就能找出两种方法来，往上走耗费的步数多，在bfs过程中也是后来达到的点，所以bfs第一次到两个加粗的0的时候，耗费步数少，但是推的次数多，而题目中要求最小的推数，与走的步数无关，所以这点必须更新并且入队列更新其他的点，如果我们没有把以前的标记消除，导致入队列失败，更新失败，答案出错。
最后一句话总结，在队列实现dp的过程中，一定记着把以前的标记消除，让新的点入队列，更新其他的状态，才能得到最后的最优解。
代码如下：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10
#define INF 999999999
int dp[maxn][maxn][maxn][maxn],n,m,maps[maxn][maxn];
int go[][] = {{,},{-,},{,},{,-}};
int vis[maxn][maxn][maxn][maxn],endx,endy;
struct Node
{
int x1,y1,x2,y2;
Node () {};
Node(int xx1,int yy1,int xx2,int yy2)
{
x1 = xx1;
y1 = yy1;
x2 = xx2;
y2 = yy2;
}
};
void mark(Node a)
{
vis[a.x1][a.y1][a.x2][a.y2] = ;
}
bool ok(int x,int y)
{
return (x>=&&x<n && y>=&&y<m && maps[x][y]!=);
}
int bfs(Node start)
{
queue<Node> que;
memset(vis,,sizeof(vis));
while(!que.empty()) que.pop();
que.push(start);
dp[start.x1][start.y1][start.x2][start.y2] = ;
//mark(start);
while(!que.empty())
{
Node now = que.front();
que.pop();
int x1 = now.x1,y1 = now.y1;
int x2 = now.x2,y2 = now.y2;
vis[x1][y1][x2][y2] = ;///进入队列，消除标记
int xx1,xx2,yy1,yy2;
for(int i = ; i < ; i++)
{
xx1 = x1 + go[i][];
yy1 = y1 + go[i][];
if(ok(xx1,yy1))
{
if(xx1 == x2 && yy1 == y2)
{
xx2 = x2 + go[i][];
yy2 = y2 + go[i][];
if(ok(xx2,yy2))
{
if(dp[xx1][yy1][xx2][yy2]==- || dp[xx1][yy1][xx2][yy2]>dp[x1][y1][x2][y2]+)///第一层检验
{
dp[xx1][yy1][xx2][yy2] = dp[x1][y1][x2][y2]+;///更新当前点状态
if(!vis[xx1][yy1][xx2][yy2])
{
Node nxt(xx1,yy1,xx2,yy2);
mark(nxt);///进入队列，更新其他点
que.push(nxt);
}
} }
}
else
{
if(dp[xx1][yy1][x2][y2]== - || dp[xx1][yy1][x2][y2]>dp[x1][y1][x2][y2])
{
dp[xx1][yy1][x2][y2] = dp[x1][y1][x2][y2];
if(!vis[xx1][yy1][x2][y2])
{
Node nxt(xx1,yy1,x2,y2);
mark(nxt);
que.push(nxt);
}
}
}
}
}
}
int ans = INF;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
//printf("dp[%d][%d] = %d\n",i,j,dp[i][j][endx][endy]);
if(dp[i][j][endx][endy] != -)
ans = min(ans,dp[i][j][endx][endy]);
}
}
if(ans != INF) return ans;
return -;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
if(n+m == ) break;
Node start;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
scanf("%d",&maps[i][j]);
if(maps[i][j] == )
{
start.x2 = i;
start.y2 = j;
}
if(maps[i][j] == )
{
start.x1 = i;
start.y1 = j;
}
if(maps[i][j] == )
{
endx = i;
endy = j;
}
}
}
memset(dp,-,sizeof(dp));
int ans = bfs(start);
printf("%d\n",ans);
}
return ;
}