本文共 1356 字，大约阅读时间需要 4 分钟。
题目链接：
题目大意：
天使的朋友要去救天使，a是天使，r 是朋友，x是卫兵。每走一步需要时间1，打倒卫兵需要另外的时间1，问救到天使所用的最少时间。注意存在救不到的情况。
思路：
BFS搜索，由于打倒卫兵时间为2，所以用BFS+优先队列做，每次出队时间最少的拓展，每个格子只走一次才是最优解
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 typedef long long ll;14 const int maxn = 2e2 + 10;15 const int INF = 1e9 + 7;16 int T, n, m, cases;17 int dir[][2] = { 1,0,0,1,-1,0,0,-1};18 struct node19 {20 int x, y, time;21 bool operator <(const node& a)const22 {23 return time > a.time;24 }25 node(){}26 node(int x, int y, int time):x(x), y(y), time(time){}27 };28 char Map[maxn][maxn];29 bool vis[maxn][maxn];30 bool judge(int x, int y)31 {32 return (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && Map[x][y] != '#');33 }34 void bfs(int x, int y)35 {36 memset(vis, 0, sizeof(vis));37 priority_queue q;38 q.push(node(x, y, 0));39 vis[x][y] = 1;40 while(!q.empty())41 {42 node now = q.top();43 q.pop();44 if(Map[now.x][now.y] == 'r')45 {46 cout< < > n >> m)69 {70 int sx, sy;71 for(int i = 0; i < n; i++)72 {73 cin >> Map[i];74 for(int j = 0; j < m; j++)if(Map[i][j] == 'a')sx = i, sy = j;75 }76 bfs(sx, sy);77 }78 return 0;79 }
转载于:https://www.cnblogs.com/fzl194/p/8746070.html