7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........
13
题意：给你一个图，‘#’代表墙， ‘.’代表路，‘x’代表是士兵。‘a’代表是终点，‘r’是起点，上下左右移动，每移动一步时间加1，遇到士兵要再加1，求需要的最少的
时间。
bfs+priority_queue
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
const int M = 205;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
using namespace std;
char map[M][M];
bool vis[M][M];
int n, m;
struct node{
int step;
int x, y;
bool operator < (const node & a) const {
return step > a.step;
}
};
node st, en;
bool limit(node s){
return (s.x >=0 && s.x < n&& s.y >= 0&& s.y < m&& map[s.x][s.y] != '#');
}
bool bfs(){
memset(vis, 0, sizeof(vis));
vis[st.x][st.y] = 1;
priority_queue<node >q;
q.push(st);
while(!q.empty()){
node temp = q.top();
q.pop();
for(int i = 0; i < 4; ++ i){
node cur = temp;
cur.x += dx[i]; cur.y += dy[i];
if(cur.x == en.x&& cur.y == en.y){
printf("%d\n", cur.step+1); return 1;
}
if(!vis[cur.x][cur.y]&&limit(cur)){
vis[cur.x][cur.y] = 1;
if(map[cur.x][cur.y] != '.'){
cur.step += 2;
}
else cur.step ++;
q.push(cur);
}
}
}
return 0;
}
int main(){
while(scanf("%d%d", &n, &m) == 2){
for(int i = 0; i < n; ++ i){
//cin >> map[i];
scanf("%s", map[i]);
for(int j = 0; j < m; ++ j)
if(map[i][j] == 'a'){
en.x = i; en.y = j;
}
else if(map[i][j] == 'r'){
st.x = i; st.y = j; st.step = 0;
}
}
bool flag = bfs();
if(!flag) printf("Poor ANGEL has to stay in the prison all his life.\n");
}
return 0;
} 原文：http://blog.csdn.net/shengweisong/article/details/44180519