原题链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1815
分析题意可知，这是一道变形的最短路径问题，通过寻找总作战次数最少的路线来求出最终结果
通过广度搜索加上贪心算法的思维来求出答案。其中为了优化搜索时间，使用了优先队列的贪心思维，而不使用优先队列的话，可能面临超时的问题，且会大大增加算法的复杂度。
个人源代码：
#include <iostream> #include <cstdio> #include <queue> using namespace std; int cla_s[26]; //记录大写字母对应的战斗次数 char a[1005][1005]; //记录矩阵 bool visited[1005][1005]; //标记是否进行过访问 int dire[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; //四个方向 ，上下左右 int n,m; //矩阵的行数和列数 struct node { int x,y; //节点坐标 long long co; //记录着走到当前结点的最少战斗次数 }; bool operator<(const node &a,const node &b) { //运算符重载，便于使用优先队列 return a.co>b.co; } node sta; //开始结点 bool is_band(node a) { //判断当前结点是否是边界 if (a.x==1 || a.x==n) return true; if (a.y==1 || a.y==m) return true; return false; } void BFS() { //广度搜索算法函数 node cur,pre; priority_queue<node> q; //优先队列，根据重载的运算符进行排序 sta.co=0; visited[sta.x][sta.y]=true; q.push(sta); while (!q.empty()) { pre=q.top(); q.pop(); if (is_band(pre)) { printf("%lld\n",pre.co); break; } for (int i=0; i<4; i++) { cur.x=pre.x+dire[i][0]; cur.y=pre.y+dire[i][1]; if (cur.x<1 || cur.x>n || cur.y<1 || cur.y>m) continue; //当前结点越界，跳过 cur.co=pre.co+cla_s[a[cur.x][cur.y]-'A']; //更行当前的结点战斗次数 if (visited[cur.x][cur.y]) continue; visited[cur.x][cur.y] = true; q.push(cur); } } } int main() { int T; cin>>T; char cls; int tim; char ss[1010]; while (T--) { int c; scanf ("%d%d%d",&c,&m,&n); while (c--) { cin>>cls>>tim; cla_s[cls-'A'] = tim; } for (int i=1; i<=n; i++) { scanf ("%s",ss); for (int j=1; j<=m; j++) { a[i][j] = ss[j-1]; visited[i][j]=false; if (a[i][j]=='E') { sta.x=i; sta.y=j; } } } BFS(); } return 0; }