较难的bfs
有两种方法做
一种双重bfs：
主bfs是箱子 还要通过dfs判断人是否能到箱子后面
用inmap函数的好处。。
箱子要用三位数组来标记 因为箱子可以回到原来到过的地方 因为推的方向不同 （第三位来表示方向）
并且地图无需改变（一些人在结构体里自带一份地图）
这题箱子的位置 对人来是是墙 不可越过 用设置vis2来实现 非常巧妙
用全局flag来代替dfs中的bool 方便很多 也不容易出错
#include<bits/stdc++.h>
using namespace std; int n,m,m1[][],vis[][][],vis2[][];
int sx,sy,ex,ey,rx1,ry1;
int dx[]={,,,-};
int dy[]={,,-,};
int flag=; struct node
{
int x,y,d,rx,ry;
node(int x=,int y=,int d=,int rx=,int ry=):x(x),y(y),d(d),rx(rx),ry(ry){}
}; bool inmap(int a,int b)
{
if(a<||a>n||b<||b>m||m1[a][b]==)
return false;
return true; } void bfs1( int sx, int sy,int ex,int ey)
{ if(sx==ex&&sy==ey) {flag=;return ;}
if(flag==)return;//值得学习
for(int i=;i<;i++)
{ if(vis2[sx+dx[i]][sy+dy[i]]==&&inmap(sx+dx[i],sy+dy[i]))
{
//printf("%d %d \n",sx+dx[i],sy+dy[i]);
vis2[sx+dx[i]][sy+dy[i]]=;
bfs1(sx+dx[i],sy+dy[i],ex,ey); } } } void bfs()
{ memset(vis,,sizeof(vis));
memset(vis2,,sizeof(vis2));
node u(sx,sy,,rx1,ry1);
queue<node>q;
q.push(u); while(!q.empty())
{ u=q.front();q.pop();
// printf("%d %d %d\n",u.x,u.y,u.d);
if(u.x==ex&&u.y==ey){printf("%d\n",u.d);return;} for(int i=;i<;i++)
{
node v(u.x+dx[i],u.y+dy[i],u.d+,u.rx,u.ry);//用自加是错的 if(inmap(u.x-dx[i],u.y-dy[i])&&inmap(v.x,v.y)&&vis[v.x][v.y][i]==)
{
flag=;
memset(vis2,,sizeof(vis2));
vis2[u.rx][u.ry]=;
vis2[u.x][u.y]=;//非常关键！！！箱子也是障碍！！！
bfs1(u.rx,u.ry,u.x-dx[i],u.y-dy[i]); if(flag)
{
vis[v.x][v.y][i]=;
v.rx=u.x-dx[i];
v.ry=u.y-dy[i];
q.push(v);
}
}
}
}
printf("-1\n");return ; }
int main()
{
int cas;scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
// printf("%d %d\n",n,m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&m1[i][j]);
if(m1[i][j]==){ex=i;ey=j;}
if(m1[i][j]==){sx=i;sy=j;}
if(m1[i][j]==){rx1=i;ry1=j;} }
// printf("%d %d\n",sx,sy);
bfs(); } return ;
}
还有一种方法是一次BFS 优先队列 用四维数组来标记人和箱子的座标 然后人疯狂乱走 如果人走到了箱子上了 就相当于推动了一次
回顾：
一定要用优先队列 不然的话是以人走的步数为基准
还有一定要注意 队列里面的优先级是反的！！！！
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 9
#define inf 0x3f3f3f3f int dx[]={,,,-};
int dy[]={,-,,};
int sx,sy,ex,ey,rx,ry;
int n,m;
int mp[N][N]; bool inmap(int x,int y)
{
return x>=&&x<=n&&y>=&&y<=m;
} struct node
{
int x,y,d,rx,ry;
bool operator <(const node &h)const{
return d>h.d;
}
}; int vis[N][N][N][N]; void bfs()
{
memset(vis,,sizeof vis);
node u,v;
u.x=sx;
u.y=sy;
u.d=;
u.rx=rx;
u.ry=ry;
priority_queue<node>q;
q.push(u);
vis[sx][sy][rx][ry]=;
while(!q.empty())
{
u=q.top();q.pop(); if( mp[u.x][u.y]== ){printf("%d\n",u.d);return ;} for(int i=;i<;i++)
{
v=u;
v.rx+=dx[i];
v.ry+=dy[i];
if( inmap(v.rx,v.ry) &&mp[v.rx][v.ry]!=)
{
if(v.rx==v.x&&v.ry==v.y&& inmap(v.x+dx[i],v.y+dy[i] )&&mp[v.x+dx[i]][v.y+dy[i]]!= )
{
v.x+=dx[i];
v.y+=dy[i];
v.d+=;
}
if(!vis[v.x][v.y][v.rx][v.ry] )
{
q.push(v);
vis[v.x][v.y][v.rx][v.ry]=;
}
}
}
}
printf("-1\n");
} int main()
{
int cas;cin>>cas;
while(cas--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&mp[i][j]);
int t=mp[i][j];
if(t==){rx=i;ry=j;}
if(t==){sx=i;sy=j;}
}
bfs();
}
return ;
}