HDU 1254 推箱子

题目链接~~>

                    开始做这题时先是想了几天，想出来方法了（没去写），之后认真看了一下，照以前的思路写了一下，有一些样例过不了，标记出现问题，想了好久的标记还是没想出来一种好的标记方法，最后还是忍不住问了度娘一下，一看……我怎么没想出来呢！！！

                  做题总结：首先有想法就应该去实现，不要整天想而不去实现，其次是想不出来再想（坚持不住的时候，再坚持一下！）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int n,m,rx,ry ;
     
    
   

    

     

    
    

     

      int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
     
    
   

    

     

    
    

     

      int _dx[4]={-1,1,0,0},_dy[4]={0,0,-1,1} ;//反方向 这不错！
     
    
   

    

     

    
    

     

      int vis[10][10],g[10][10],vix[10][10][10][10] ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,cx,cy,bu ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      int  _bfs(int x,int y,int ax,int ay)//看是否能搜索到人
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<node>q ;
     
    
   

    

     

    
    

     

       node current,next ;
     
    
   

    

     

    
    

     
 memset(vis,0,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       current.x=x ;
     
    
   

    

     

    
    

     

       current.y=y ;
     
    
   

    

     

    
    

     

       q.push(current) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       current=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(current.x==ax&¤t.y==ay)
     
    
   

    

     

    
    

     
 return 1 ;
     
    
   

    

     

    
    

     
 for(int i=0;i<4;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=current.x+dx[i] ;
     
    
   

    

     

    
    

     

       next.y=current.y+dy[i] ;
     
    
   

    

     

    
    

     
 if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&g[next.x][next.y]!=1&&!vis[next.x][next.y])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[next.x][next.y]=1 ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y,int ax,int ay)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<zhang>q ;
     
    
   

    

     

    
    

     

       zhang current,next ;
     
    
   

    

     

    
    

     
 int fm ;
     
    
   

    

     

    
    

     
 memset(vix,0,sizeof(vix)) ;
     
    
   

    

     

    
    

     

       current.x=x ;
     
    
   

    

     

    
    

     

       current.y=y ;
     
    
   

    

     

    
    

     

       current.cx=ax ;
     
    
   

    

     

    
    

     

       current.cy=ay ;
     
    
   

    

     

    
    

     

       vix[x][y][ax][ay]=1 ;//考虑到这点很重要，可以避免重复走一样的 
     
    
   

    

     

    
    

     

       current.bu=0 ;
     
    
   

    

     

    
    

     

       q.push(current) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       current=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(current.x==rx&¤t.y==ry)
     
    
   

    

     

    
    

     
 return current.bu ;
     
    
   

    

     

    
    

     
 for(int i=0;i<4;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=current.x+dx[i] ;
     
    
   

    

     

    
    

     

       next.y=current.y+dy[i] ;
     
    
   

    

     

    
    

     

       next.cx=current.x+_dx[i] ;
     
    
   

    

     

    
    

     

       next.cy=current.y+_dy[i] ;
     
    
   

    

     

    
    

     
 int z=g[current.x][current.y] ;
     
    
   

    

     

    
    

     

       fm=0 ;
     
    
   

    

     

    
    

     
 if(next.cx>=0&&next.cy>=0&&next.cx<n&&next.cy<m&&g[next.cx][next.cy]!=1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[current.x][current.y]=1 ;
     
    
   

    

     

    
    

     

       fm=_bfs(next.cx,next.cy,current.cx,current.cy) ;
     
    
   

    

     

    
    

     

       g[current.x][current.y]=z ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!vix[next.x][next.y][next.cx][next.cy]&&next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&g[next.x][next.y]!=1&&fm)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vix[next.x][next.y][next.cx][next.cy]=1 ;
     
    
   

    

     

    
    

     

       next.bu=current.bu+1 ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i,j,ex,ey,qx,qy ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m) ;
     
    
   

    

     

    
    

     
 for(i=0;i<n;i++)
     
    
   

    

     

    
    

     
 for(j=0;j<m;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&g[i][j]) ;
     
    
   

    

     

    
    

     
 if(g[i][j]==2)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ex=i ;
     
    
   

    

     

    
    

     

       ey=j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(g[i][j]==3)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       rx=i ;
     
    
   

    

     

    
    

     

       ry=j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(g[i][j]==4)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       qx=i ;
     
    
   

    

     

    
    

     

       qy=j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",bfs(ex,ey,qx,qy)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/12103611