#include<bits/stdc++.h>
using namespace std;
int t;
int m,n;
int g[9][9];
int s[9][9][9][9];bool vis[9][9];
int vx[]={0,0,1,-1};int vy[]={-1,1,0,0};
signed main(){
cin>>t;
while(t--){
cin>>m>>n;
int sx,sy,bx,by,ex,ey;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(g[i][j]==2) bx=i,by=j;
//cout<<11111111111111<<endl;
if(g[i][j]==3) ex=i,ey=j;
if(g[i][j]==4) sx=i,sy=j;
}
}fill(vis[0],vis[0]+9*9,0);
fill(s[0][0][0],s[0][0][0]+9*9*9*9,INT_MAX);
deque<int> q;
int ax,ay;
s[sx][sy][bx][by]=0;
g[sx][sy]=1;
//cout<<sx<<sy<<endl;
q.push_back(sx);
q.push_back(sy);
q.push_back(bx);
q.push_back(by);
while(!q.empty()){
int x=q.front();
q.pop_front();
int y=q.front();
q.pop_front();
int u=q.front();
q.pop_front();
int v=q.front();
q.pop_front();
if(u==sx && v==sy){
ax=x;ay=y;
break;
}
//if(vis[x][y]) continue;
for(int i=0;i<4;i++){
int nx=vx[i]+x;
int ny=vy[i]+y;
if(nx<1 || nx>n) continue;
if(ny<1 || ny>m) continue;
//if(s[nx][ny][u][v]!=INT_MAX) continue;
//if(vis[u][v]) continue;
if(g[nx][ny]==1) continue;
//vis[u][v]=1;
//cout<<nx<<' '<<ny<<endl;
if(nx==u && ny==v){;
int nu=u+vx[i];
int nv=v+vy[i];cout<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<nu<<' '<<nv<<endl;
if(nu<1 || nu>n) continue;
if(nv<1 || nv>m) continue;
if(g[nu][nv]==1) continue;
if(s[nx][ny][nu][nv]!=INT_MAX) continue;
q.push_back(nx);
q.push_back(ny);
q.push_back(nu);
q.push_back(nv);
s[nx][ny][u][v]=s[x][y][nu][nv]+1;
}
else{
if(s[nx][ny][u][v]!=INT_MAX) continue;
q.push_front(u);
q.push_front(v);
q.push_front(nx);
q.push_front(ny);
s[nx][ny][u][v]=s[x][y][u][v];
}
}
}
cout<<s[ax][ay][ex][ey]<<endl;
}
return 0;
}
2 个赞
#include<bits/stdc++.h>
using namespace std;
int n,m,Map[10][10];
int book[10][10][10][10];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
struct node{
int sx,sy,ex,ey,step;
bool operator<(const node &a)const{
return a.step<step;
}
};
int check(int x,int y){
if(x<1||x>n||y<1||y>m||Map[x][y]==1)
return 1;
return 0;
}
void bfs(int x1,int y1,int x2,int y2){
memset(book,0,sizeof(book));
priority_queue<node>Q;
node p,q;
q.sx=x1,q.sy=y1,q.ex=x2,q.ey=y2,q.step=0;
Q.push(q);
book[x1][y1][x2][y2]=1;
while(!Q.empty()){
p=Q.top();
Q.pop();
if(Map[p.ex][p.ey]==3){
printf("%d\n",p.step);
return;
}
for(int i=0; i<4; i++){
q.sx=p.sx+dir[i][0];
q.sy=p.sy+dir[i][1];
if(check(q.sx,q.sy))continue;
q.ex=p.ex,q.ey=p.ey,q.step=p.step;
if(q.sx==q.ex&&q.sy==q.ey){
q.ex=p.ex+dir[i][0];
q.ey=p.ey+dir[i][1];
if(check(q.ex,q.ey))continue;
q.step++;
}
if(!book[q.sx][q.sy][q.ex][q.ey]){
book[q.sx][q.sy][q.ex][q.ey]=1;
Q.push(q);
}
}
}
printf("-1\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int x1,y1,x2,y2,x3,y3;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&Map[i][j]);
if(Map[i][j]==4)x1=i,y1=j;
else if(Map[i][j]==3)x2=i,y2=j;
else if(Map[i][j]==2)x3=i,y3=j;
}
}
bfs(x1,y1,x3,y3);
}
}
2 个赞
我推荐你使用如下代码：（先搜人能到的地方，再搜箱子）
易于理解
#include<bits/stdc++.h>
using namespace std;
bool dt[10][10],v[10][10]={0},vren[10][10]={0};
int n,m,sx,sy,ex,ey,rx,ry,k,t;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfsren(int x,int y){
vren[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(dt[nx][ny]==1||vren[nx][ny]==1) continue;
dfsren(nx,ny);
}
return;
}
struct xx{
int x,y,step;
};
void bfs(){
queue<xx> q;
q.push(xx{sx,sy,0});
while(q.size()>0){
xx now=q.front();
q.pop();
if(now.x==ex&&now.y==ey){
printf("%d\n",now.step);
return;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(dt[nx][ny]==1||v[nx][ny]==1) continue;
if(vren[now.x-dx[i]][now.y-dy[i]]==0) continue;//如果人不能到推箱子的反方向就跳过
v[nx][ny]=1;
q.push(xx{nx,ny,now.step+1});
}
}
printf("%d\n",-1);
return;
}
int main(){
cin>>t;
while(t--){
for(int i=0;i<=10;i++){
for(int j=0;j<=10;j++){
vren[i][j]=0;
v[i][j]=0;
}
}
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&k);
if(k==1) dt[i][j]=1;
else dt[i][j]=0;
if(k==2){
sx=i;
sy=j;
}else if(k==3){
ex=i;
ey=j;
}else{
rx=i;
ry=j;
}
}
}
dfsren(rx,ry);
bfs();
}
return 0;
}
2 个赞