UVA 10047 The Moncycle

题目链接~~>

做题感悟：这道题属于一般的搜索题，要注意一些细节，输出的时候检查是否与样例一样。

解题思路：这题终点在标记上面，因为题目中有方向和颜色限制，so~> 需要一个四维数组来标记，如果做过POJ上的左手定则这题应该很容易做。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 30 + 10 ;
     
    
   

    

     

    
    

     

      int n,m ;
     
    
   

    

     

    
    

     

      char s[MX][MX] ;
     
    
   

    

     

    
    

     

      bool vis[MX][MX][MX][MX] ;
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      int dt[4][4]={{2,4,4},{3,4,4},{0,4,4},{1,4,4}} ;
     
    
   

    

     

    
    

     

      int dw[4][4]={{0,2,3},{1,2,3},{2,0,1},{3,0,1}} ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,step,drt,clr ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      bool judge(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(x<0||y<0||x>=n||y>=m||s[x][y]=='#')
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y) // 东西南北 0 1 2 3
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<node>q ;
     
    
   

    

     

    
    

     

       node curt,next ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       curt.x=x ;
     
    
   

    

     

    
    

     

       curt.y=y ;
     
    
   

    

     

    
    

     

       curt.step=0 ; // 时间
     
    
   

    

     

    
    

     

       curt.clr=0 ; // 颜色
     
    
   

    

     

    
    

     

       curt.drt=3 ; // 方向
     
    
   

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     

       vis[x][y][0][3]=true ; // 颜色+方向
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=q.front() ;
     
    
   

    

     

    
    

     
 if(s[curt.x][curt.y]=='T'&&curt.clr==0)
     
    
   

    

     

    
    

     
 return curt.step ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 int cnt=curt.drt ;// 主方向
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int tx=dt[cnt][i] ;
     
    
   

    

     

    
    

     

       next.x=curt.x+dx[tx] ;
     
    
   

    

     

    
    

     

       next.y=curt.y+dy[tx] ;
     
    
   

    

     

    
    

     
 if(i)
     
    
   

    

     

    
    

     

       next.clr=curt.clr ;
     
    
   

    

     

    
    

     
 else next.clr=(curt.clr+1)%5 ;
     
    
   

    

     

    
    

     

       next.step=curt.step+1 ;
     
    
   

    

     

    
    

     

       next.drt=dw[cnt][i] ;
     
    
   

    

     

    
    

     
 if(judge(next.x,next.y)) // 判断出界
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 if(vis[next.x][next.y][next.clr][next.drt]) continue ;
     
    
   

    

     

    
    

     

       vis[next.x][next.y][next.clr][next.drt]=true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int sx,sy,cse=1 ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d",&n,&m)&&(n+m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx=i ;
     
    
   

    

     

    
    

     

       sy=j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int mx=bfs(sx,sy) ;
     
    
   

    

     

    
    

     
 if(cse!=1)  cout<<endl ;
     
    
   

    

     

    
    

     
 cout<<"Case #"<<cse++<<endl ;
     
    
   

    

     

    
    

     
 if(mx==-1)
     
    
   

    

     

    
    

     
 cout<<"destination not reachable"<<endl ;
     
    
   

    

     

    
    

     
 else   cout<<"minimum time = "<<mx<<" sec"<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

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

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