传送门：

题意：就是一个箱子的推箱子，问箱子最少走多少步到达目的地。

因为我c++实训打算写个推箱子游戏，看见有这题就过来打一下。。。。

这题两种解法

第一种：就是普通的bfs，只是记录状态有四个值，分别是人的坐标和箱子的坐标，由于n很小，所以vis[n][n][n][n]内存还是可以接受的。

1 // Cease to struggle and you cease to live 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
             
            
           
          
         
        
       
      

第二种：第二种解法是在网上学来的。因为箱子最少步，所以肯定是对箱子bfs，但是箱子移动的前提是人能够到箱子的后面，所以在箱子的bfs中，箱子每次移动要对人跑一边bfs，看看人能不能到达箱子移动的反方向（注意，人不能穿墙或者穿过箱子）

1 #include
      
        2 using namespace std; 3 struct node{ 4     int px,py,bx,by; 5     int step; 6 }; 7 int dx[]={
    0,0,-1,1}; 8 int dy[]={
    1,-1,0,0}; 9 bool vis[10][10][5];10 bool fg[10][10];11 int mp[10][10];12 int n,m;13 bool bfs(node fr,node to){14     memset(fg,0,sizeof(fg));15     queue
       
         q;16     q.push(fr);17     while(!q.empty()){18         node u=q.front();19         q.pop();20         if(u.px==to.px && u.py==to.py) return true;21         for(int i=0;i<4;++i){22             int xx=u.px+dx[i],yy=u.py+dy[i];23             if(xx<1 || xx>n || yy<1 || yy>m) continue;24             if(fg[xx][yy]) continue;25             if(mp[xx][yy]==1) continue;26             if(xx==fr.bx && yy==fr.by) continue;27             fg[xx][yy]=1;28             node tem=u;29             tem.px=xx;tem.py=yy;30             q.push(tem);31         }32     }33     return false;34 }35 int main(){36     int T;scanf("%d",&T);37     for(int cas=1;cas<=T;++cas){38         scanf("%d%d",&n,&m);39         memset(vis,0,sizeof(vis));40         node st;41         st.step=0;42         for(int i=1;i<=n;++i){43             for(int j=1;j<=m;++j){44                 scanf("%d",&mp[i][j]);45                 if(mp[i][j]==4){46                     st.px=i;st.py=j;47                 }48                 if(mp[i][j]==2){49                     st.bx=i;st.by=j;50                 }51             }52         }53         queue
        
          Q;54         Q.push(st);55         int ans=0x3f3f3f3f;56         while(!Q.empty()){57             node u=Q.front();58             Q.pop();59             if(mp[u.bx][u.by]==3){60                 ans=min(ans,u.step);61             }62             //cerr<
         
          <<' '<
          
           <
           
            <
            
             n || byy<1 || byy >m) continue;67 if(vis[bxx][byy][i]) continue;68 if(pxx<1 || pxx>n || pyy<1 || pyy>m) continue;69 if(mp[bxx][byy]==1 || mp[pxx][pyy]==1) continue;70 node box=u,peo=u;71 peo.px=pxx;peo.py=pyy;72 if(bfs(u,peo)){73 vis[bxx][byy][i]=1;74 box.bx=bxx;box.by=byy;75 box.px=u.bx;box.py=u.by;76 box.step=u.step+1;77 Q.push(box);78 }79 }80 }81 if(ans==0x3f3f3f3f) puts("-1");82 else printf("%d\n",ans);83 }84 return 0;85 }
            
           
          
         
        
       
      

现在就六月份了，考前一个月用来复习了，也就是说打完这题，以及明天的训练赛，我就彻底不碰键盘一个月了。想想还是有点不舍得的。那么这题就当做是我的封建盘一个月的收山之作吧。哈哈哈哈。