这个题目需要注意以下几点：
1）注意界线问题，箱子和人不可以越界。
2)需要判断人是否可以到达人推箱子的指定位置。
3）不可以用箱子作为标记，因为箱子可以走原来走过的地方，我们用箱子和人推箱子的方向来进行重判。定义一个Hash[8][8][8][8]来标记。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#define MAX_SIZE 8
bool Hash[MAX_SIZE][MAX_SIZE][MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE];
int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
int N,M;
struct Point {
int x, y;
bool operator==(const Point&b)const {
return x == b.x&&y == b.y;
}
bool Isleg() {
if (x<1 || x>N || y<1 || y>M || map[x][y] == 1)
return false;
return true;
}
};
struct BOX {
Point person;
Point box;
int step;
};
int BFS();
int main() {
int i, j,T,res;
scanf("%d",&T);
while (T--) {
scanf("%d%d", &N, &M);
for (i = 1; i <= N; i++)
for (j = 1; j <= M; j++)
scanf("%d", &map[i][j]);
res = BFS();
printf("%d
", res);
}
return 0;
}
bool DFS(Point &person, Point &des,Point &box) { //判断人是否可以到达指定位置
int k;
memset(visit, 0, MAX_SIZE*sizeof(visit[0]));
visit[person.x][person.y] = 1;
stack<Point> S;
S.push(person);
Point next, pos;
while (!S.empty()) {
pos = S.top();
S.pop();
if (pos == des)
return true;
for (k = 0; k < 4; k++) {
next = pos;
next.x += dir[k][0];
next.y += dir[k][1];
if (next.Isleg() && !(next==box) && !visit[next.x][next.y]) {
visit[next.x][next.y] = 1;
S.push(next);
}
}
}
return false;
}
Point serch(int x) {
Point res;
int i, j;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++)
if (x == map[i][j]) {
res.x = i;
res.y = j;
}
}
return res;
}
int BFS() {
int i, j,k,l;
for (i = 1; i < MAX_SIZE; i++)
for (j = 1; j < MAX_SIZE; j++)
for (k = 1; k < MAX_SIZE; k++)
for (l = 1; l < MAX_SIZE; l++)
Hash[i][j][l][k] = 0;
BOX B,Box;
B.person = serch(4);
B.box = serch(2);
B.step = 0;
Point des, next,peo;
des = serch(3);
queue<BOX> Q;
Q.push(B);
while (!Q.empty()) {
B = Q.front();
Q.pop();
if (B.box == des)
return B.step;
B.step++;
Box = B;
for (k = 0; k < 4; k++) {
next = peo=B.box;
next.x += dir[k][0];
next.y += dir[k][1];
peo.x -= dir[k][0];
peo.y -= dir[k][1];
if (peo.Isleg() && next.Isleg() &&DFS(B.person,peo,B.box)&&!Hash[peo.x][peo.y][next.x][next.y]) {
Hash[peo.x][peo.y][next.x][next.y] = 1;
Box.person = B.box;
Box.box = next;
Q.push(Box);
}
}
}
return -1;
}