題意：
Angel被傳說中神秘的邪惡的Moligpy人抓住了！他被關在一個迷宮中。迷宮的長、寬不超過200。 迷宮中有不可以越過的牆以及監獄的看守。
Angel的朋友帶了一些救援隊來到了迷宮中。他們的任務是：接近Angel。我們假設接近Angel就是到達Angel所在的位置。
假設移動需要1單位時間，殺死一個看守也需要1單位時間。到達一個格子以後，如果該格子有看守，則一定要殺死。交給你的任務是，最少要多少單位時間，才能到達Angel所在的地方？（只能向上、下、左、右4個方向移動）
Input
該題含有多組測試數據。每組測試數據第一行二個整數n，m。表示迷宮的大小為n*m (N, M <= 200) 。 以後n行，每行m個時字符。其中“#”代表牆，“.”表示可以移動，“x”表示看守，“a”表示Angel，“r”表示救援隊伍。字母均為小寫。
Output
一行，代表救出Angel的最短時間。如果救援小組永遠不能達到Angel處，則輸出“Poor ANGEL has to stay in the prison all his life.”
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output
13
分析：
(N, M <= 200) 首先想到的是BFS, {P.S 有人dfs 0MS AC~~}
可能有多個’r’，而’a’只有一個，從’a’開始搜，找到的第一個’r’即為所求。
由於題目中增加了“x”表示看守這一個東東，經過“x”需要多耗一個單位時間。因此如果我們采用普通的寬搜，在第k層搜到了目標，但是耗時可能不止k個單位時間｛有可能這條路徑經過了“x”｝。
對此我有三個想法：
1、采用優先隊列（按到達該點的時候），這樣就能保證最先擴展到目標狀態的時候，耗時是最小的。
2、把當擴展到“x”點時，把他放到與他耗時一樣的那一層。這樣也能保證到擴展到目標狀態時，耗時是最小的。
code1:(優先隊列)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n, m;
char map[205][205];
int sx, sy;
bool flag;
struct node {
int x, y, step;
bool operator <(const node & t) const
{
return step>t.step;
}
};
int dx[]= {-1,0,0,1};
int dy[]= {0,-1,1,0};
void bfs() {
node now, tmp;
int i,xx,yy;
priority_queue<node> q;
now.x = sx, now.y = sy, now.step = 0;
map[sx][sy] = '#';
q.push(now);
while(!q.empty()) {
now = q.top();
q.pop();
// cout<<now.x<<" "<<now.y<<" "<<now.step<<endl;
for(i=0; i<4; i++) {
xx = now.x +dx[i];
yy = now.y +dy[i];
if(xx<0||xx>=n||yy<0||yy>=m||map[xx][yy]=='#') continue;
if(map[xx][yy]=='r') {
cout<<now.step+1<<endl;
flag = true;
return ;
}
if(map[xx][yy]=='x') {
tmp.x =xx, tmp.y = yy, tmp.step = now.step+2;
q.push(tmp);
} else {
tmp.x =xx, tmp.y = yy, tmp.step = now.step+1;
q.push(tmp);
}
map[xx][yy] = '#';
}
}
}
int main() {
int i, j;
while(~scanf("%d%d",&n,&m)) {
for(i=0; i<n; i++)
for(j=0; j<m; j++) {
cin>>map[i][j];
if(map[i][j]=='a')
sx=i,sy=j;
}
flag = false;
bfs();
if(!flag) printf("Poor ANGEL has to stay in the prison all his life.\n");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n, m;
char map[205][205];
int sx, sy;
bool flag;
struct node {
int x, y, step;
bool operator <(const node & t) const
{
return step>t.step;
}
};
int dx[]= {-1,0,0,1};
int dy[]= {0,-1,1,0};
void bfs() {
node now, tmp;
int i,xx,yy;
priority_queue<node> q;
now.x = sx, now.y = sy, now.step = 0;
map[sx][sy] = '#';
q.push(now);
while(!q.empty()) {
now = q.top();
q.pop();
// cout<<now.x<<" "<<now.y<<" "<<now.step<<endl;
for(i=0; i<4; i++) {
xx = now.x +dx[i];
yy = now.y +dy[i];
if(xx<0||xx>=n||yy<0||yy>=m||map[xx][yy]=='#') continue;
if(map[xx][yy]=='r') {
cout<<now.step+1<<endl;
flag = true;
return ;
}
if(map[xx][yy]=='x') {
tmp.x =xx, tmp.y = yy, tmp.step = now.step+2;
q.push(tmp);
} else {
tmp.x =xx, tmp.y = yy, tmp.step = now.step+1;
q.push(tmp);
}
map[xx][yy] = '#';
}
}
}
int main() {
int i, j;
while(~scanf("%d%d",&n,&m)) {
for(i=0; i<n; i++)
for(j=0; j<m; j++) {
cin>>map[i][j];
if(map[i][j]=='a')
sx=i,sy=j;
}
flag = false;
bfs();
if(!flag) printf("Poor ANGEL has to stay in the prison all his life.\n");
}
return 0;
}
code2:(想法2)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node
{
int x, y;
int step;
};
queue<node> q;
int N, M, prove, sx, sy, visit[202][202];
char map[202][202];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1,};
int check(int x, int y)
{
if(x < 0 || x >= N || y < 0 || y >= M)
return 0;
else
return 1;
}
void BFS()
{
while(!q.empty())
q.pop();
node s, e;
memset(visit, 0, sizeof(visit));
s.step = 0; s.x = sx; s.y = sy;
q.push(s);
visit[s.x][s.y] = 1;
while(!q.empty())
{
s = q.front();
q.pop();
if(map[s.x][s.y] == 'a')
{
cout << s.step << endl;
prove =1;
}
//如取出的是在有警衛的格子中，即殺掉警衛再次進入隊列
if(map[s.x][s.y] == 'x')
{
map[s.x][s.y] = '.';
s.step += 1;
q.push(s);
continue;
}
for(int i = 0; i < 4; i++)
{
e.x = s.x + dx[i]; e.y = s.y + dy[i];
if(!check(e.x, e.y) || visit[e.x][e.y]
|| map[e.x][e.y] == '#')
continue;
e.step = s.step + 1;
q.push(e);
visit[e.x][e.y] = 1;
}
}
}
int main()
{
while(cin >> N >> M)
{
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
{
cin >> map[i][j];
if(map[i][j] == 'r')
{ sx = i; sy = j; }
}
prove = 0;
BFS();
if(!prove)
cout << "Poor ANGEL has to stay in the prison all his life." << endl;
}
return 0;
}
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node
{
int x, y;
int step;
};
queue<node> q;
int N, M, prove, sx, sy, visit[202][202];
char map[202][202];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1,};
int check(int x, int y)
{
if(x < 0 || x >= N || y < 0 || y >= M)
return 0;
else
return 1;
}
void BFS()
{
while(!q.empty())
q.pop();
node s, e;
memset(visit, 0, sizeof(visit));
s.step = 0; s.x = sx; s.y = sy;
q.push(s);
visit[s.x][s.y] = 1;
while(!q.empty())
{
s = q.front();
q.pop();
if(map[s.x][s.y] == 'a')
{
cout << s.step << endl;
prove =1;
}
//如取出的是在有警衛的格子中，即殺掉警衛再次進入隊列
if(map[s.x][s.y] == 'x')
{
map[s.x][s.y] = '.';
s.step += 1;
q.push(s);
continue;
}
for(int i = 0; i < 4; i++)
{
e.x = s.x + dx[i]; e.y = s.y + dy[i];
if(!check(e.x, e.y) || visit[e.x][e.y]
|| map[e.x][e.y] == '#')
continue;
e.step = s.step + 1;
q.push(e);
visit[e.x][e.y] = 1;
}
}
}
int main()
{
while(cin >> N >> M)
{
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
{
cin >> map[i][j];
if(map[i][j] == 'r')
{ sx = i; sy = j; }
}
prove = 0;
BFS();
if(!prove)
cout << "Poor ANGEL has to stay in the prison all his life." << endl;
}
return 0;
}
