拯救行动
题目描述： 现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要 1 个单位时间，杀死一个守卫需要花费额外的 1 个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。
给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。
输入格式 1、两个整数代表 N 和 M, (N,M≤200). 2、随后 N 行，每行有 M 个字符。"@" 代表道路，“a” 代表公主，“r” 代表骑士，“x” 代表守卫, “#” 代表墙壁。
输出格式 如果拯救行动成功，输出一个整数，表示行动的最短时间。 如果不可能成功，输出 “Impossible”。
输出时每行末尾的多余空格，不影响答案正确性
样例输入 7 8 #@#####@ #@a#@@r@ #@@#x@@@ @@#@@#@# #@@@##@@ @#@@@@@@ @@@@@@@@ 样例输出 13
解题思路:
此题在走到x和@时的花费是不同的，但bfs是按顺序进行搜索的，因此可能搜索到结果时的时间不是最短，此时就需要用到优先队列，时间短的先出队
代码：
#include <iostream> #include <queue> using namespace std; int n,m,f,sx,sy,ex,ey; char map[205][205]; int flag[205][205]; int tr[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct node { int x; int y; int s; node (int xx,int yy,int ss) { x=xx; y=yy; s=ss; } friend bool operator < (node a,node b) { return a.s>b.s; } }; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>map[i][j]; if(map[i][j]=='r') { sx=i; sy=j; } if(map[i][j]=='a') { ex=i; ey=j; } } } priority_queue<node> q; node temp(sx,sy,0); q.push(temp); flag[sx][sy]=1; while(!q.empty()) { temp=q.top(); q.pop(); for(int i=0;i<4;i++) { int tx=temp.x+tr[i][0]; int ty=temp.y+tr[i][1]; int ss=temp.s+1; if(tx>0&&tx<=n&&ty>0&&ty<=m) { if(tx==ex&&ty==ey) { f=1; cout<<ss<<endl; break; } if(!flag[tx][ty]&&map[tx][ty]=='@') { q.push(node(tx,ty,ss)); flag[tx][ty]=1; } if(!flag[tx][ty]&&map[tx][ty]=='x') { q.push(node(tx,ty,ss+1)); flag[tx][ty]=1; } } } if(f==1) break; } if(f==0) cout<<"Impossible"<<endl; return 0; }