本文主要是介绍hdu1242 Rescue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/............................................................................................................................................................................................\
题目解析：从起始点a开始寻找到r的最短的路径，在最短的路径上如果遇到x，可以花一秒的时间将x杀死，然后通过
解这一题可以用bfs，通过队列一步步的寻找，入队，出队，直到找到r输出用的时间的最小值，或者找
不到。（应该是bfs的简单点的题目吧）。
\............................................................................................................................................................................................/
#include<stdio.h>
#include <iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<list>
#include<vector>
#include<cstdlib>
#include<cstdio>
#include <queue>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define MAX 201
char map[MAX][MAX];
int mark[MAX][MAX];
int si,sj,n,m,flag;struct node
{int x;int y;int step;
} point;int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; /*控制方向*/void bfs()
{queue<node>q;/*定义队列*/node t,c;int k;point.x=si;point.y=sj;point.step=0;mark[si][sj]=1;/*标记走过的路*/flag=0;q.push(point);/*入队列的起始点*/while(!q.empty())/*判断队列是否为空，队列不为空*/{c=q.front();/*取队头元素*/q.pop();/*队头元素出队*/if(map[c.x][c.y]=='x')/*遇到兵，时间加1*/{c.step++;map[c.x][c.y]='.';q.push(c);}else{for( k=0; k<4; k++)/*扫描四周，寻找路径*/{t.x=c.x+dir[k][0];t.y=c.y+dir[k][1];t.step=c.step+1;if(map[t.x][t.y]!='#'&&mark[t.x][t.y]==0&&t.x>0&&t.y>0&&t.x<=n&&t.y<=m)/*判别方向*/{if(map[t.x][t.y]=='a')/*找到天使，就输出*/{printf("%d\n",t.step);flag=1;return ;}/*如果没有找到，将点入队继续寻找*/mark[t.x][t.y]=1;q.push(t);}}}}if(!flag)/*没有找到，而且也没有路课走*/printf("Poor ANGEL has to stay in the prison all his life.\n");
}int main()
{int i,j;freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>map[i][j];if(map[i][j]=='r')/*找到起始点*/{si=i;sj=j;}mark[i][j]=0;/*初始化标记数组*/}bfs();}return 0;
}
这篇关于hdu1242 Rescue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
