HDU 2531 Catch him

题目链接~~>

               这题坑了我好久，还是那句话只要你真心去做一定能想出办法来。这题办法倒是想出来了，但是我标记的是身体的全部，每次都这样，只有检测到全部被标记时才不继续往下搜索，测试数据试很多也没找出错误来，最后才知道只要标记一个就行，而且必须一直标记同一个。。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int r ;
     
    
   

    

     

    
    

     

      int n,m ;
     
    
   

    

     

    
    

     

      int vx[105],vy[105] ;
     
    
   

    

     

    
    

     

      char s[105][105] ;
     
    
   

    

     

    
    

     

      int vis[105][105] ;
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x[25],y[25],bu ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      int bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<zhang>q ;
     
    
   

    

     

    
    

     

       zhang current,next ;
     
    
   

    

     

    
    

     
 int i,j,k ;
     
    
   

    

     

    
    

     
 int nx,ny ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       current.x[i]=vx[i] ;
     
    
   

    

     

    
    

     

       current.y[i]=vy[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       vis[current.x[0]][current.y[0]]=1 ;//每次标记开始那一点
     
    
   

    

     

    
    

     

       current.bu=0 ;
     
    
   

    

     

    
    

     

       q.push(current) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       current=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int  p=0,ret=0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

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

    

     

    
    

     

       nx=next.x[j] ;
     
    
   

    

     

    
    

     

       ny=next.y[j] ;
     
    
   

    

     

    
    

     
 if(!j&&vis[nx][ny])
     
    
   

    

     

    
    

     

       ret=1 ;
     
    
   

    

     

    
    

     
 if(nx<0||nx>=n||ny<0||ny>=m||s[nx][ny]=='O')
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ret=1 ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(s[nx][ny]=='Q')
     
    
   

    

     

    
    

     

       p=1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(ret)
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     
 if(p)
     
    
   

    

     

    
    

     
 return current.bu+1 ;
     
    
   

    

     

    
    

     
 for(k=0;k<r;k++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

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

    

     

    
    

     

       nx=next.x[k] ;
     
    
   

    

     

    
    

     

       ny=next.y[k] ;
     
    
   

    

     

    
    

     
 if(!k)
     
    
   

    

     

    
    

     

       vis[nx][ny]=1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       next.bu=current.bu+1 ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j ;
     
    
   

    

     

    
    

     
 while(scanf("%d%d",&n,&m)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!n&&!m)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       r=0 ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s",s[i]) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(s[i][j]=='D')
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vx[r]=i ;
     
    
   

    

     

    
    

     

       vy[r]=j ;
     
    
   

    

     

    
    

     

       r++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int mx=bfs() ;
     
    
   

    

     

    
    

     
 if(mx==-1)
     
    
   

    

     

    
    

     
 printf("Impossible\n") ;
     
    
   

    

     

    
    

     
 else printf("%d\n",mx) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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