HDU 5040 Instrusive - c++编程基础

TOP

HDU 5040 Instrusive

2015-07-24 05:20:01 来源: 作者: 【大中小】浏览:8次

题目链接~~>

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

解题思路：

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

代码：

#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    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
                   
                     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 #"<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：acdream 1222 Quantization Probl..	下一篇：HDU 1754 I Hate It （线段树 &am..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: