HDU 5040 Instrusive

题目链接~~>

做题感悟：这题在网络赛的时候没有解出来，当时最后才写的有点慌了，so~>思路一点不清楚。

解题思路：

              这题首先弄清楚在走每一步的时候是人先走，还是摄像头先走，当然是人先走，如果一个人从 A ---> B ,那么需要判断前一秒A 和 B 是否被摄像头照到，因为人先走，如果曾被摄像头找到，那么走过去会被发现，这样可以选择等一秒，下一秒同样再判断一次，如果还是不可以，就需要带着箱子走。还要注意时间第一秒时摄像头转到先一个方向。因为时间不是都加 1 ，需要用优先队列，同时一个点可以去多次，需要用时间标记所为第三维。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const INT mod = 1000000007 ;
     
    
   

    

     

    
    

     

      const int MY = 100 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 500 + 5 ;
     
    
   

    

     

    
    

     

      int n ,ex ,ey ;
     
    
   

    

     

    
    

     

      char s[MX][MX] ;
     
    
   

    

     

    
    

     

      bool dir[MX][MX][4] ,vis[MX][MX][4] ;
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x ,y ,step ;
     
    
   

    

     

    
    

     
 friend bool operator < (const node& a ,const node& b)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return  a.step > b.step ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      int bfs(int x ,int y) // 人先走，摄像头再走 !!!!!
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int sx ,sy ,step ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 priority_queue<node> q ;
     
    
   

    

     

    
    

     

       node curt ,next ;
     
    
   

    

     

    
    

     

       curt.x = x ;
     
    
   

    

     

    
    

     

       curt.y = y ;
     
    
   

    

     

    
    

     

       curt.step = 0 ;
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       q.push(curt) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       curt = q.top() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

     
 if(ex == curt.x && ey == curt.y)
     
    
   

    

     

    
    

     
 return curt.step ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x = sx = curt.x + dx[i] ;
     
    
   

    

     

    
    

     

       next.y = sy = curt.y + dy[i] ;
     
    
   

    

     

    
    

     

       next.step = step = curt.step + 1 ;
     
    
   

    

     

    
    

     
 if(sx >= 0 && sx < n && sy >= 0 && sy < n && s[sx][sy] != '#') // 判断出界
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dir[sx][sy][curt.step%4]|| dir[curt.x][curt.y][curt.step%4]) // 判断当前点前一秒 和 下一个点前一秒是否曾被照到
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!dir[sx][sy][step%4] && !dir[curt.x][curt.y][step%4])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.step = curt.step + 2 ;
     
    
   

    

     

    
    

     
 if(!vis[sx][sy][next.step%4])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[sx][sy][next.step%4] = true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.step = curt.step + 3 ;
     
    
   

    

     

    
    

     
 if(!vis[sx][sy][next.step%4])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[sx][sy][next.step%4] = true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(!vis[sx][sy][step%4])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[sx][sy][step%4] = true ;
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init(int x ,int y) // 处理摄像头方向
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int sx ,sy ,key = 0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       sx = x + dx[i] ;
     
    
   

    

     

    
    

     

       sy = y + dy[i] ;
     
    
   

    

     

    
    

     
 if(s[x][y] == 'E')
     
    
   

    

     

    
    

     

       key = 3 ;
     
    
   

    

     

    
    

     
 else if(s[x][y] == 'S')
     
    
   

    

     

    
    

     

       key = 2 ;
     
    
   

    

     

    
    

     
 else if(s[x][y] == 'W')
     
    
   

    

     

    
    

     

       key = 1 ;
     
    
   

    

     

    
    

     
 if(sx >= 0 && sx < n && sy >= 0 && sy < n && s[sx][sy] != '#')
     
    
   

    

     

    
    

     

       dir[sx][sy][(key+i)%4] = true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       s[x][y] = '.' ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx ,sx ,sy ,cse = 1 ;
     
    
   

    

     

    
    

     
 scanf("%d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cin>>n ;
     
    
   

    

     

    
    

     
 memset(dir ,false ,sizeof(dir)) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cin>>s[i] ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx = i ; sy = j ;
     
    
   

    

     

    
    

     

       s[i][j] = '.' ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(s[i][j] == 'T')
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ex = i ; ey = j ;
     
    
   

    

     

    
    

     

       s[i][j] = '.' ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(s[i][j] == 'N' || s[i][j] == 'S' || s[i][j] == 'W' || s[i][j] == 'E')
     
    
   

    

     

    
    

     

       init(i ,j) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<"Case #"<<cse++<<": "<<bfs(sx ,sy)<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
  
 

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

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