路障(BFS)

技术文章 8个月前 完美者
1,310 0

标签:can   https   元素   应该   包含   problem   span   cond   obs   

P3395 路障

看来是我太菜了耗时大半个小时才做出来,看来搜索还是8太行,需要多做题。

这道题数据很弱,一些特殊情况如走到某一个点正好被路障砸到是不用考虑的。

由于每一个点都包含 X, Y 二维信息,我使用了 pair 进行存储坐标。并且将其放入队列当中,这样可以保证每次都依次取出输入时的路障顺序。当然,还需要一个保存待走的点的队列,当然此处我也使用了Pair进行保存。这道题的难点可能就是在何时以及如何放置路障,本道题在于选择好下一个点之后才能进行路障放置,并且需要注意路障队列可能为空,那么此时这个队列就相当于被废弃了。

代码如下:

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 int all, n;
 8 bool vis[1010][1010];
 9 int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
10 typedef pair<int, int> P;
11 queue <P> obstacle, path;
12 
13 int bfs(){
14     path.push({1, 1});
15     vis[1][1] = true;
16     while(path.size()){
17         auto now = path.front();
18         path.pop();
19         if(now.first == n && now.second == n)
20             return 1;
21         P t;
22         for(int i = 0; i < 4; i ++){
23             int tx = now.first + dir[i][0];
24             int ty = now.second + dir[i][1];
25             //应该先判断下一步是否被标记过,如果被标记过那么跳出,如果没被标记过,那么
26             //先取出障碍队列的当前队首元素,将其代表的点设置为已经访问,同时还需要将
27             //这个人当前已经走的路线也标记上已经访问过。
28             //然后将下一个要走的点放到队列里面
29             //走  到  下一个点新的路障才会出现,不会出现走到这一步正好被砸到的情况
30             if(!vis[tx][ty] && tx > 0 && tx <= n && ty > 0 && ty <= n){          
31                 //不应该在这里pop,因为这只是一次放置障碍
32                 //obstacle.pop();
33                 if(obstacle.size()){
34                     t = obstacle.front();
35                     vis[t.first][t.second] = true;
36                 }
37                 vis[tx][ty] = true;
38                 path.push({tx, ty});
39             }   
40         }
41         if(obstacle.size()){
42             obstacle.pop();
43         }
44         
45     }
46     return 0;
47 }
48 int main(){
49     scanf("%d", &all);
50     while(all --){
51         memset(vis, 0, sizeof vis);
52         while(obstacle.size())
53             obstacle.pop();
54         while(path.size())
55             path.pop();
56         scanf("%d", &n);
57         for(int i = 1; i <= 2 * n - 2; i ++){
58             int x, y;
59             scanf("%d%d", &x, &y);
60             obstacle.push({x, y});
61         }
62         int ans = bfs();
63         if(ans)
64             printf("Yes\n");
65         else
66             printf("No\n");
67     }
68 
69     return 0;
70 }

 

路障(BFS)

标签:can   https   元素   应该   包含   problem   span   cond   obs   

原文地址:https://www.cnblogs.com/pureayu/p/13904302.html

版权声明:完美者 发表于 2020-10-31 2:23:48。
转载请注明:路障(BFS) | 完美导航

暂无评论

暂无评论...