HDU 2364 Escape

题目链接~~>

做题感悟：这种题只要将方向作为第三维标记即可，但是这题因为漏想了一个地方导致改了老半天。

解题思路：只要将方向作为第三维标记，还要注意如果左右能走就不走前，只有左右都为石头时才走前，且不能反方向走（可以走走过的路）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define LEN sizeof(struct node)
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      #define lld __int64
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const double INF = 999999999 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-4 ;
     
    
   

    

     

    
    

     

      const lld  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int MX = 81 ;
     
    
   

    

     

    
    

     

      int n,m ;
     
    
   

    

     

    
    

     

      char s[MX][MX] ;
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ; // 下 0 上 1 右 2 左 3
     
    
   

    

     

    
    

     

      int dr[4][4]={{1,0,2},{0,1,3},{2,3,0},{3,2,1}} ;// 东 西 南 北 0 1 2 3
     
    
   

    

     

    
    

     

      int dc[4][4]={{3,2,0},{2,3,1},{0,1,2},{1,0,3}} ; // 走完后对应的方向
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,step,cnt ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      bool search(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int sx,sy,cnt ;
     
    
   

    

     

    
    

     
 queue<node>q ;
     
    
   

    

     

    
    

     

       node curt,next ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       curt.x=x ;
     
    
   

    

     

    
    

     

       curt.y=y ;
     
    
   

    

     

    
    

     

       curt.step=0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<4 ;i++) // 初始化四个方向
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt.cnt=i ;
     
    
   

    

     

    
    

     

       vis[x][y][i]=true ;
     
    
   

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     

       x=curt.x ;  y=curt.y ;
     
    
   

    

     

    
    

     

       cnt=curt.cnt ;  // cnt 方向
     
    
   

    

     

    
    

     
 if(!x||!y||x==n-1||y==m-1)
     
    
   

    

     

    
    

     
 return curt.step ;
     
    
   

    

     

    
    

     
 bool fx=false ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int z=dr[cnt][i] ;
     
    
   

    

     

    
    

     

       next.x=sx=x+dx[z] ;
     
    
   

    

     

    
    

     

       next.y=sy=y+dy[z] ;
     
    
   

    

     

    
    

     

       next.step=curt.step+1 ;
     
    
   

    

     

    
    

     
 if(search(sx,sy)&&(!fx||i<2))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int mx=dc[cnt][i] ; // 方向
     
    
   

    

     

    
    

     
 if(!vis[sx][sy][mx])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.cnt=mx ;
     
    
   

    

     

    
    

     

       vis[sx][sy][mx]=true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       fx=true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else fx=true ; // fx 标记左右是否可走，开始忘记了这个！！！
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx,sx,sy ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(s[i][j]=='@') //记录起始位置
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx=i ;
     
    
   

    

     

    
    

     

       sy=j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",bfs(sx,sy)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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