【BFS+优先级队列】Rescue

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/I

【题意】

给定一个n*m的迷宫，A的多个小伙伴R要去营救A，问需要时间最少的小伙伴是多长时间
遇到'.'需要1分钟，遇到'x'需要两分钟，遇到'#'不能走

【思路】

这道题的关键是遇到'.'和遇到'x'需要的时间不一样，所以不能用平常的BFS找最短路
vis数组不再是true和false两个状态来标记是否已经走过，而是记录最小步数的值
不再是vis是false就加入队列，而是vis小于最小步数加入队列
因为有多个R营救一个A，所以是以A为起点BFS

【Accepted】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 
 9 using namespace std;
10 
11 int n,m;
12 const int maxn=2e2+3;
13 const int inf=0x3f3f3f3f;
14 char str[maxn][maxn];
15 //bool vis[maxn][maxn];
16 int vis[maxn][maxn];
17 struct node
18 {
19     int x;
20     int y;
21     int step;
22     node(){}
23     node(int _x,int _y,int _s):x(_x),y(_y),step(_s){}
24     friend bool operator<(node nd1,node nd2)
25     {
26         return nd2.step<nd1.step;
27     }
28 }nd[maxn];
29 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
30 bool check(int x,int y)
31 {
32     if(str[x][y]=='#') return false;
33     if(x<0||x>=n||y<0||y>=m) return false;
34     return true;
35 }
36 int BFS(int x,int y)
37 {
38     priority_queue<node> Q;
39     Q.push(node(x,y,0));
40     vis[x][y]=0;
41     while(!Q.empty())
42     {
43         node q=Q.top();
44         Q.pop();
45         if(str[q.x][q.y]=='r') return q.step;
46         for(int i=0;i<4;i++)
47         {
48             int x=q.x+dir[i][0];
49             int y=q.y+dir[i][1];
50             if(check(x,y))
51             {
52                 int s;
53                 if(str[x][y]=='x') s=q.step+2;
54                 else s=q.step+1;
55                 if(s<vis[x][y]) 
56                 {
57                     vis[x][y]=s;
58                     Q.push(node(x,y,s));
59                 }
60             }
61         }
62     }
63     return -1;
64 }
65 int main()
66 {
67     while(~scanf("%d%d",&n,&m))
68     {
69         memset(vis,inf,sizeof(vis));
70         int x,y;
71         for(int i=0;i<n;i++)
72         {
73             scanf("%s",str[i]);
74             for(int k=0;k<m;k++)
75             {
76                 if(str[i][k]=='a')
77                 {
78                     x=i;
79                     y=k;    
80                 }
81             }
82         }
83         int ans=BFS(x,y);
84         if(ans==-1)
85         {
86             puts("Poor ANGEL has to stay in the prison all his life.");
87         }
88         else
89         {
90             printf("%d
",ans);
91         }
92     }
93     return 0;
94  }

BFS+优先级队列