hdu 1242 Rescue

题目链接：

题目大意：这一题是典型的搜索题，为了寻找到最佳路径，我们可以反向找，这样得到的结果就是我们需要要求的结果。在搜索方法上使用优先队列来解决。

代码如下：

#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<queue>
using namespace std;
#define INF 10000000
const int maxn=210;
char s[maxn][maxn];
int n,m,sx,sy,ex,ey;
int q[4][2]={1,0,-1,0,0,-1,0,1};
struct node
{
int x,y,step;
friend bool operator<(node a,node b)
{
return a.step>b.step;
}
};
void bfs()
{
node beg,cur,pre;
priority_queue<node>Q;//定义一个优先队列
beg.x=sx;
beg.y=sy;
beg.step=0;
Q.push(beg);
while(!Q.empty())
{
cur=Q.top();
Q.pop();
for(int i=0;i<4;i++)
{
pre=cur;
int xx=pre.x+q[i][0];
int yy=pre.y+q[i][1];
if(xx<0||xx>=n||yy<0||yy>=m||s[xx][yy]=='#')//限定边界
continue;
else if(s[xx][yy]=='x')//遇到x相当于消耗两倍的时间
pre.step++;
pre.x=xx;
pre.y=yy;
pre.step++;
if(s[xx][yy]=='r')//找到终点
{
printf("%dn",pre.step);
return;
}
s[pre.x][pre.y]='#';//标志已经寻找过了，不能再次走这个点
Q.push(pre);
}
}
printf("Poor ANGEL has to stay in the prison all his life.n");
return ;
}
int main(void)
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%c",&s[i][j]);
if(s[i][j]=='a')//找到起点
{
sx=i;
sy=j;
}
}
getchar();
}
bfs();
}
system("Pause");
return 0;
}

最后

以上就是缓慢小土豆为你收集整理的hdu 1242 Rescue的全部内容，希望文章能够帮你解决hdu 1242 Rescue所遇到的程序开发问题。

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