「拯救天使」HDU [ 拯救天使 ]——优先队列（结构体）+BFS

拯救天使

HDU——拯救天使：

Problem Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and guards in the prison. Angel's friends want to save Angel. Their task is: APProach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards. You have to calculate the Minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M. Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8#.#####.#.a#..r.#..#x.....#..#.##...##...#..............

Sample Output

====================================

题目大意：天使被关在监狱中，有n个伙伴去救他，给出伙伴们及天使的位置，求在给定规则下小伙伴到达天使所在位置的最短时间，有一个到即可。

拿到这道题目，很明显是最短路问题，所以首先考虑使用BFS，但因为考虑到最短的路径下并不一定得到最小的时间，因此，我们使用优先队列来代替普通队列（注意一下结构体类型的优先队列怎么重载“<”即可）。对于优先队列解决最短路问题，我们可以这么考虑：如果在相同的路径长度下，某点用的时间要长一些，那么就把这一点放入下一层路径中（即路径长度+1的那一层）。

其次，对于本题，或者是bfs+广搜的问题，还有一些注意事项：

①、对于本题，要注意多组测试数据这个问题，在每完成一组数据之后，我们要重新更新标记数组、队列以及。。。

②、还是本题，我们要注意在一组测试数据中，起始位置可能有多个，如果我们依次查找的话，会非常复杂，甚至可能会超时。因此，我们用终点位置代替起始位置来搜索。（可以说是一个小技巧）。

③、最短路问题：顾名思义，我们要找那条最短的路径，并且这条路“有且仅有”一条（尽管可能有多条）。所以我们在到达某一点时用标记数组标记下这个点，表示我们已经找到到达这个点的最短路，且无法再通过其他的点到达该点，即使可能两者所通过的路径长度一样。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[206][206];
int f[206][206]; //可以不用f数组，因为bfs+优先队列所走的的每一步都是当前的最短路径，找到终点即任务结束，没有需要比较的地方。
int b[6]={0,1,-1,0,0};
int c[6]={0,0,0,1,-1};
bool flag[206][206];
struct prison
{
    int x;
    int y;
	int time;
	friend bool operator < (prison a,prison b)        //结构体+优先队列一般要重载小于号“<”;
	{
		return a.time>b.time;
	}
}p,q;
int bfs(int zx,int zy)
{
    priority_queue < prison > Q;          //注意队列定义的位置；
	p.x=zx;p.y=zy;
	p.time=0;
    Q.push(p);
    flag[zx][zy]=1;        //标记起始点；
    f[zx][zy]=0;
    while(!Q.empty())
    {
        q=Q.top();    //优先队列与普通队列的区别之一，队首元素top & front;
		//cout<<q.x<<q.y<<q.time<<endl;
        Q.pop();
        for(int i=1;i<=4;++i)
        {
            int x=q.x+b[i];
            int y=q.y+c[i];
            if(x>=1&&x<=n&&y>=1&&y<=m&&flag[x][y]==0)
            {
                p.x=x;
                p.y=y;


                flag[x][y]=1;
                f[x][y]=f[q.x][q.y]+1;    //重复，这里完全可以不用f数组，因为我们不需要记忆化存储所有点，用到的只有当前点与上一个点。
	        if(a[x][y]=='x')f[x][y]++;

		p.time=f[x][y];
		if(a[x][y]=='r')return f[x][y];//找到一个终点，即任务结束，即找到最短路。
		Q.push(p);

            }
        }
    }
	return 0;

}
int main()
{

  while( cin>>n>>m )
  {
	memset(flag,0,sizeof(flag));  //每一次都要重新更新这几个数组。
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	int zx,zy,ans;
    for(int i=1;i<=n;++i)
     {

	   getchar();       //稍微注意一下字符输入的空格问题；
	   for(int j=1;j<=m;++j)
            {

            scanf("%c",&a[i][j]);
            if(a[i][j]=='a') //用终点代替起点，解决多起点问题。
            {
                zx=i;
                zy=j;
            }
            if(a[i][j]=='#')
            {
                flag[i][j]=1;
            }


         }

	  }
	  ans=bfs(zx,zy);

    if(ans)cout<<ans<<endl;
    else cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
  }
    return 0;

}

the end；

HDU [ 拯救天使 ]——优先队列（结构体）+BFS

拯救天使

相关阅读

栏目导航

推荐阅读

热门阅读