1242 Rescue

http://acm.hdu.edu.cn/showproblem.php?pid=1242

采用bfs算法，并且需要注意：朋友是有很多的，搜索时要a去寻找r.

#include <iostream>
#include<queue>
#include<string.h>
using namespace std;
char map[202][202];
int visit[202][202];
int c,r,i,j,minn=10000,ai,aj;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
bool check(int x, int y)
{
if(x >= 0 && x<r && y>= 0 && y< c && !visit[x][y])
//cin c r
return true;
return false;
}
struct M
{
int x, y,sum;
}st,en;
queue<M> que;
void bfs()
{
while(!que.empty())
{
st = que.front();
que.pop();
if(map[st.x][st.y] == 'r')
{
if(st.sum < minn)
{
minn = st.sum;
}
}
for(i = 0; i<4; i++)
{
en.x = st.x + dir[i][0];
en.y = st.y + dir[i][1];
if(check(en.x,en.y) && (map[en.x][en.y] == 'r'||map[en.x][en.y] == 'x'||map[en.x][en.y] == '.'))
{
if(map[en.x][en.y] == 'x')
{
en.sum = st.sum + 2;
visit[en.x][en.y] = 1;
}
else
{
en.sum = st.sum + 1;
visit[en.x][en.y] = 1;
}
que.push(en);
}
}
}
}
int main()
{
int i,j;
while(cin>>r>>c)
{
memset(map,0,sizeof(map));
for(i = 0; i<r; i++)
{
for(j = 0; j<c; j++)
{
cin>>map[i][j];
if(map[i][j] == 'a')
{
ai = i; aj = j;
map[i][j] = '.';
}
}
}
memset(visit,0,sizeof(visit));
while(!que.empty())
que.pop();
st.x = ai;
st.y = aj;
st.sum = 0;
minn = 10000;
visit[ai][aj] = 1;
que.push(st);
bfs();
if(minn == 10000)
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout<<minn<<endl;
}
return 0;
}

最后

以上就是秀丽荷花为你收集整理的1242 Rescue的全部内容，希望文章能够帮你解决1242 Rescue所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。