题目链接：

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

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             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
            
             
               >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
              
               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
               
                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\n",ans); 95 } 96 return 0; 97 } 98 99 100 101 102