http://acm.hdu.edu.cn/showproblem.php?pid=1254
暴搜，状态是四维的（箱子和人的坐标），向一个方向推箱子还要判断人能否走到推的位置，1A
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; int n, m;
int tx, ty;
int vis[][][][],vis1[][];
int M[][]; struct node {
int x, y, px, py, step;
node() {};
node(int x, int y, int px, int py, int step) :
x(x), y(y), px(px), py(py), step(step) {
};
}; node st; int dx[]={,-,,};
int dy[]={,,,-}; struct point {
int x, y;
point(int x, int y) :
x(x), y(y) {
};
}; int bfs1(int x, int y, int px, int py) {
queue <point> q;
q.push(point(px, py));
while(!q.empty()) {
point u = q.front();
q.pop();
if(u.x == x && u.y == y) return ;
for(int i = ; i < ; i++){
int xx = u.x + dx[i];
int yy = u.y + dy[i];
if(xx < || yy < || xx >=n || yy >= m) continue ;
if(M[xx][yy] == || vis1[xx][yy]) continue;
vis1[xx][yy] = ;
q.push(point(xx, yy));
}
}
return ;
}; int bfs2() {
queue <node> q;
memset(vis, , sizeof(vis));
q.push(st);
vis[st.x][st.y][st.px][st.py] = ;
while(!q.empty()) {
node u = q.front();
q.pop();
if(u.x == tx && u.y == ty) return u.step;
for(int i = ; i < ; i++) {
int xx = u.x + dx[i];
int yy = u.y + dy[i];
int px = u.x - dx[i];
int py = u.y - dy[i];
if(xx < || yy < || xx >= n || yy >=m || px < || py < || px >= n || py >= m) continue;
if(M[xx][yy] == || M[px][py] == ) continue;
if(vis[xx][yy][px][py]) continue;
memset(vis1, , sizeof(vis1));
vis1[u.x][u.y] = ;
int flag = bfs1(px, py, u.px, u.py);
vis1[u.x][u.y] = ;
if(flag) {
vis[xx][yy][px][py] = ;
q.push(node(xx, yy, px, py, u.step + ));
}
}
}
return -;
}; int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
scanf("%d", &M[i][j]);
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
if(M[i][j] == )
tx = i, ty = j;
if(M[i][j] == )
st.x = i, st.y = j;
if(M[i][j] == )
st.px = i, st.py = j;
}
}
st.step = ;
printf("%d\n", bfs2());
}
return ;
}