題意：推箱子游戲，在一個M*N的房間裡有一個箱子和一個搬運工,搬運工的工作就是把箱子推到指定的位置，求最少的推箱子的次數，如果不能完成則輸出-1。
思路：帶嵌套的BFS~第一層BFS箱子，箱子每次移動前要再BFS一下人，看人能不能走到推動箱子的位置。
注意：//因為人的位置不同時箱子可能可以到同一個位置兩次，所以開4維(兩維是箱子位置，兩維是人的位置)數組標記。
[cpp]
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node{
int x,y,cnt;
int px,py;
}now,tmp,pnow,ptmp;
queue<struct node>q;//BFS箱子的隊列
queue<struct node>p;//BFS人的隊列
int m,n;
int maze[11][11];
bool vis[11][11][11][11];
bool pvis[11][11];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool p_ok()
{
if(ptmp.x>=0&&ptmp.y>=0&&ptmp.x<m&&ptmp.y<n&&maze[ptmp.x][ptmp.y]!=1&&!(ptmp.x==now.x&&ptmp.y==now.y)&&!pvis[ptmp.x][ptmp.y])
return true;
else
return false;
}
bool p_bfs(int k)//簡單的BFS，i為箱子要去的方向
{
while(!p.empty())
p.pop();
memset(pvis,false,sizeof(pvis));
pnow.x=tmp.px;pnow.y=tmp.py;
if(pnow.x==now.x-dx[k]&&pnow.y==now.y-dy[k])//特殊判斷人就在箱子邊上且正好是要推箱子的位置的情況
return true;
pvis[pnow.x][pnow.y]=true;
p.push(pnow);
while(!p.empty())
{
pnow=p.front();
p.pop();
for(int i=0;i<4;i++)
{
ptmp=pnow;
ptmp.x+=dx[i];
ptmp.y+=dy[i];
if(p_ok())
{
if(ptmp.x==now.x-dx[k]&&ptmp.y==now.y-dy[k])
return true;
pvis[ptmp.x][ptmp.y]=true;
p.push(ptmp);
}
}
}
return false;
}
bool ok()
{
if(tmp.x>=0&&tmp.y>=0&&tmp.x<m&&tmp.y<n&&maze[tmp.x][tmp.y]!=1&&!vis[tmp.x][tmp.y][tmp.px][tmp.py])
return true;
else
return false;
}
int bfs()
{
while(!q.empty())
q.pop();
now.cnt=0;
vis[now.x][now.y][now.px][now.py]=true;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
tmp=now;
tmp.x+=dx[i];
tmp.y+=dy[i];
if(ok())
{
if(p_bfs(i))//判斷人能否走到要推箱子的位置
{
tmp.cnt++;
if(maze[tmp.x][tmp.y]==3)
return tmp.cnt;
tmp.px=now.x;tmp.py=now.y;
vis[tmp.x][tmp.y][now.px][now.py]=true;
q.push(tmp);
}
}
}
}
return -1;
}
int main()
{
int t;
while(scanf("%d",&t)==1)
{
while(t--)
{
memset(vis,false,sizeof(vis));
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&maze[i][j]);
if(maze[i][j]==2){now.x=i;now.y=j;}
else if(maze[i][j]==4){now.px=i;now.py=j;}//初始化BFS箱子的第一個節點
}
}
printf("%d\n",bfs());
}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node{
int x,y,cnt;
int px,py;
}now,tmp,pnow,ptmp;
queue<struct node>q;//BFS箱子的隊列
queue<struct node>p;//BFS人的隊列
int m,n;
int maze[11][11];
bool vis[11][11][11][11];
bool pvis[11][11];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool p_ok()
{
if(ptmp.x>=0&&ptmp.y>=0&&ptmp.x<m&&ptmp.y<n&&maze[ptmp.x][ptmp.y]!=1&&!(ptmp.x==now.x&&ptmp.y==now.y)&&!pvis[ptmp.x][ptmp.y])
return true;
else
return false;
}
bool p_bfs(int k)//簡單的BFS，i為箱子要去的方向
{
while(!p.empty())
p.pop();
memset(pvis,false,sizeof(pvis));
pnow.x=tmp.px;pnow.y=tmp.py;
if(pnow.x==now.x-dx[k]&&pnow.y==now.y-dy[k])//特殊判斷人就在箱子邊上且正好是要推箱子的位置的情況
return true;
pvis[pnow.x][pnow.y]=true;
p.push(pnow);
while(!p.empty())
{
pnow=p.front();
p.pop();
for(int i=0;i<4;i++)
{
ptmp=pnow;
ptmp.x+=dx[i];
ptmp.y+=dy[i];
if(p_ok())
{
if(ptmp.x==now.x-dx[k]&&ptmp.y==now.y-dy[k])
return true;
pvis[ptmp.x][ptmp.y]=true;
p.push(ptmp);
}
}
}
return false;
}
bool ok()
{
if(tmp.x>=0&&tmp.y>=0&&tmp.x<m&&tmp.y<n&&maze[tmp.x][tmp.y]!=1&&!vis[tmp.x][tmp.y][tmp.px][tmp.py])
return true;
else
return false;
}
int bfs()
{
while(!q.empty())
q.pop();
now.cnt=0;
vis[now.x][now.y][now.px][now.py]=true;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
tmp=now;
tmp.x+=dx[i];
tmp.y+=dy[i];
if(ok())
{
if(p_bfs(i))//判斷人能否走到要推箱子的位置
{
tmp.cnt++;
if(maze[tmp.x][tmp.y]==3)
return tmp.cnt;
tmp.px=now.x;tmp.py=now.y;
vis[tmp.x][tmp.y][now.px][now.py]=true;
q.push(tmp);
}
}
}
}
return -1;
}
int main()
{
int t;
while(scanf("%d",&t)==1)
{
while(t--)
{
memset(vis,false,sizeof(vis));
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&maze[i][j]);
if(maze[i][j]==2){now.x=i;now.y=j;}
else if(maze[i][j]==4){now.px=i;now.py=j;}//初始化BFS箱子的第一個節點
}
}
printf("%d\n",bfs());
}
}
return 0;
}
