推箱子 HDU1254 （bfs）

较难的bfs

有两种方法做

一种双重bfs：

主bfs是箱子还要通过dfs判断人是否能到箱子后面

用inmap函数的好处。。

箱子要用三位数组来标记因为箱子可以回到原来到过的地方因为推的方向不同（第三位来表示方向）

并且地图无需改变（一些人在结构体里自带一份地图）

这题箱子的位置对人来是是墙不可越过用设置vis2来实现非常巧妙

用全局flag来代替dfs中的bool 方便很多也不容易出错

#include<bits/stdc++.h>
using namespace std;

int n,m,m1[10][10],vis[10][10][4],vis2[10][10];
int sx,sy,ex,ey,rx1,ry1;
 int dx[4]={0,1,0,-1};
int  dy[4]={1,0,-1,0};
int flag=0;

struct node
{
    int x,y,d,rx,ry;
    node(int x=0,int y=0,int d=0,int rx=0,int ry=0):x(x),y(y),d(d),rx(rx),ry(ry){}
};


bool inmap(int a,int b)
{
    if(a<1||a>n||b<1||b>m||m1[a][b]==1)
        return false;
    return true;

}

void bfs1( int sx, int sy,int ex,int ey)
{

    if(sx==ex&&sy==ey) {flag=1;return ;}
    if(flag==1)return;//值得学习
    for(int i=0;i<4;i++)
    {

        if(vis2[sx+dx[i]][sy+dy[i]]==0&&inmap(sx+dx[i],sy+dy[i]))
        {
            //printf("%d %d 
",sx+dx[i],sy+dy[i]);
            vis2[sx+dx[i]][sy+dy[i]]=1;
            bfs1(sx+dx[i],sy+dy[i],ex,ey);

        }

    }

}


void bfs()
{

    memset(vis,0,sizeof(vis));
    memset(vis2,0,sizeof(vis2));
    node u(sx,sy,0,rx1,ry1);
    queue<node>q;
    q.push(u);

    while(!q.empty())
    {

        u=q.front();q.pop();
       // printf("%d %d %d
",u.x,u.y,u.d);
        if(u.x==ex&&u.y==ey){printf("%d
",u.d);return;}

        for(int i=0;i<4;i++)
        {
            node v(u.x+dx[i],u.y+dy[i],u.d+1,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]==0)
            {
                  flag=0;
                 memset(vis2,0,sizeof(vis2));
                 vis2[u.rx][u.ry]=1;
                 vis2[u.x][u.y]=1;//非常关键！！！箱子也是障碍！！！
                 bfs1(u.rx,u.ry,u.x-dx[i],u.y-dy[i]);

                if(flag)
                  {
                    vis[v.x][v.y][i]=1;
                      v.rx=u.x-dx[i];
                      v.ry=u.y-dy[i];
                       q.push(v);
                  }
            }
        }
    }
       printf("-1
");return ;

}
int main()
{
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
       // printf("%d %d
",n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
        {
            scanf("%d",&m1[i][j]);
            if(m1[i][j]==3){ex=i;ey=j;}
            if(m1[i][j]==2){sx=i;sy=j;}
            if(m1[i][j]==4){rx1=i;ry1=j;}

        }
       // printf("%d %d
",sx,sy);
        bfs();


    }

    return 0;
}

View Code

还有一种方法是一次BFS 优先队列用四维数组来标记人和箱子的座标然后人疯狂乱走如果人走到了箱子上了就相当于推动了一次

#include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; #define N 9 #define inf 0x3f3f3f3f int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int sx,sy,ex,ey,rx,ry; int n,m; int mp[N][N]; bool inmap(int x,int y) { return x>=1&&x<=n&&y>=1&&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,0,sizeof vis); node u,v; u.x=sx; u.y=sy; u.d=0; u.rx=rx; u.ry=ry; priority_queue<node>q; q.push(u); vis[sx][sy][rx][ry]=1; while(!q.empty()) { u=q.top();q.pop(); if( mp[u.x][u.y]==3 ){printf("%d ",u.d);return ;} for(int i=0;i<4;i++) { v=u; v.rx+=dx[i]; v.ry+=dy[i]; if( inmap(v.rx,v.ry) &&mp[v.rx][v.ry]!=1) { 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]]!=1 ) { v.x+=dx[i]; v.y+=dy[i]; v.d+=1; } if(!vis[v.x][v.y][v.rx][v.ry] ) { q.push(v); vis[v.x][v.y][v.rx][v.ry]=1; } } } } printf("-1 "); } int main() { int cas;cin>>cas; while(cas--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&mp[i][j]); int t=mp[i][j]; if(t==4){rx=i;ry=j;} if(t==2){sx=i;sy=j;} } bfs(); } return 0; }

推箱子 HDU1254 （bfs）

相关推荐