loj 1377 (bfs)

题目链接：http://lightoj.com/volume_showproblem.php?problem=1377

思路：这道题只要处理好遇到"*"这种情况就可以搞定了。我们可以用一个vector向量来记录所有的“*”，然后用一个3维数组来判重，并且对于每个状态都加一个标记，判断是否需要立刻转移，值得注意的是转移过后，vector应该立刻清空。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 
  9 const int MAXN = (200 + 20);
 10 const int inf = (1 << 30);
 11 int n,m,ans;
 12 char map[MAXN][MAXN];
 13 vector<pair<int, int> >vet;
 14 
 15 struct Node{
 16     int x, y, step, pre;
 17     bool operator < (const Node &p ) const {
 18         return p.step < step;
 19     }
 20 }st;
 21 
 22 bool mark[MAXN][MAXN][2];
 23 int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
 24 
 25 void bfs()
 26 {
 27     memset(mark, false, sizeof(mark));
 28     priority_queue<Node >que;
 29     que.push(st);
 30     mark[st.x][st.y][0]=true;
 31     while(!que.empty()){
 32         Node q, p = que.top();
 33         que.pop();
 34         if(map[p.x][p.y] == 'D'){
 35             ans = p.step;
 36             return ;
 37         }
 38         if(map[p.x][p.y] == '*'){
 39             bool flag = false;
 40             for(int i = 0; i < (int)vet.size(); i++){
 41                 pair<int, int>pp = vet[i];
 42                 if(pp.first == p.x&&pp.second == p.y){
 43                     flag = true;
 44                     continue;
 45                 }
 46                 if(!mark[pp.first][pp.second][1]){
 47                     mark[pp.first][pp.second][1] = true;
 48                     Node tmp;
 49                     tmp.x = pp.first, tmp.y = pp.second, tmp.step = p.step + 1, tmp.pre = 1;
 50                     que.push(tmp);
 51                 }
 52             }
 53             vet.clear();
 54             if(flag)vet.push_back(make_pair(p.x,p.y));
 55             if(p.pre == 0)continue;
 56         }
 57         for(int i = 0; i < 4; i++){
 58             q.x = p.x + dir[i][0];
 59             q.y = p.y + dir[i][1];
 60             if(map[q.x][q.y] == '#')continue;
 61             if(!mark[q.x][q.y][0]){
 62                 mark[q.x][q.y][0] = true;
 63                 q.step = p.step + 1;
 64                 q.pre = 0;
 65                 que.push(q);
 66             }
 67         }
 68     }
 69 }
 70     
 71 int main()
 72 {
 73     int _case,t=1;
 74     scanf("%d",&_case);
 75     while(_case--){
 76         vet.clear();
 77         scanf("%d%d",&n,&m);
 78         for(int i=1; i<=n; i++){
 79             scanf("%s", map[i] + 1);
 80             for(int j=1; j<=m; j++){
 81                  if(map[i][j] == 'P'){
 82                     st.x = i, st.y = j, st.step = 0, st.pre = 0;
 83                 }else if(map[i][j] == '*') {
 84                     vet.push_back(make_pair(i,j));
 85                 } 
 86             }
 87         }
 88         ans = inf;
 89         bfs();
 90         printf("Case %d: ", t++);
 91         if(ans == inf){
 92             puts("impossible");
 93         }else 
 94             printf("%d
",ans);
 95     }
 96     return 0;
 97 }
 98 
 99 
100 
101         
102

View Code