首先按箱子進行BFS. 然後判斷箱子所走方向的反面，人是否能到達，即對人進行DFS。。
下面是 AC代碼：
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAX = 10;
int map[MAX][MAX];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int other_dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}}; //反方向
bool vis[MAX][MAX][MAX][MAX];
bool mark[MAX][MAX];
int flag,ans;
struct node
{
int ps_x,ps_y;
int bk_x,bk_y;
int step;
int cur_map[MAX][MAX];
} s_pos;
int end_x,end_y;
int m,n;
void init()
{
s_pos.step=0;
for(int i=0; i<m; i++) for(int j=0; j<n; j++)
{
if(map[i][j]==2) s_pos.bk_x=i, s_pos.bk_y=j;
else if(map[i][j]==3) end_x=i,end_y=j;
else if(map[i][j]==4) s_pos.ps_x=i, s_pos.ps_y=j;
s_pos.cur_map[i][j]=map[i][j];
}
memset(vis,0,sizeof(vis));
}
bool cheak(int x,int y){
if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!=1) return true;
return false;
}
int can;
void dfs(int p_x,int p_y,int b_x,int b_y,int now_map[10][10]) //判斷人能否到達箱子的旁邊
{
if(can) return ;
if(p_x==b_x&&p_y==b_y) { can=1; return ;}//cout<<p_x<<" "<<p_y<<endl;
for(int i=0; i<4; i++){
int x=p_x+dir[i][0], y=p_y+dir[i][1];
if(cheak(x,y)&&now_map[x][y]!=2&&!mark[x][y]){
mark[x][y]=true; dfs(x,y,b_x,b_y,now_map; mark[x][y]=false;
}
}
}
void bfs()
{
init(); queue<node > q;
vis[s_pos.bk_x][s_pos.bk_y][s_pos.ps_x][s_pos.ps_y]=true;
q.push(s_pos);
while(!q.empty()){
node now = q.front();
q.pop();
if(now.bk_x==end_x&&now.bk_y==end_y){
flag=1,ans=now.step; return ;
}
for(int i=0; i<4; i++){
node next=now;
next.bk_x+=dir[i][0], next.bk_y+=dir[i][1];next.step+=1;
int x=now.bk_x+other_dir[i][0],y=now.bk_y+other_dir[i][1];
if(cheak(x,y)&&cheak(next.bk_x,next.bk_y)&&!vis[next.bk_x][next.bk_y][now.bk_x][now.bk_y])
{
memset(mark,0,sizeof(mark)); mark[next.ps_x][next.ps_y]=true;
can=0;
dfs(next.ps_x,next.ps_y,x,y,now.cur_map);
if(can){
vis[next.bk_x][next.bk_y][now.bk_x][now.bk_y]=true; // cout<<next.bk_x<<" "<<next.bk_y<<endl;
next.ps_x=now.bk_x;
next.ps_y=now.bk_y;
next.cur_map[next.bk_x][next.bk_y]=2;
next.cur_map[now.bk_x][now.bk_y]=0;
q.push(next);
}
}
}
}
}
int main()
{
int t,i,j;
cin>>t;
while(t--)
{
cin>>m>>n;
for(i=0; i<m; i++) for(j=0; j<n; j++) cin>>map[i][j];
flag=0;
ans=-1;
bfs();
if(flag) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
