首页 > ACM题库 > HDU-杭电 > HDU 1242 Rescue-BFS-[解题报告] C++
2013
12-04

HDU 1242 Rescue-BFS-[解题报告] C++

Rescue

问题描述 :

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.)

输入:

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.

输出:

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."

样例输入:

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

样例输出:

13

初次使用优先队列;

有的人用普通队列也能过,但是,我只能说,那是数据太水了;

普通队列能过的将类似下面两句改改顺序:

int xx[4] = {1,-1,0,0};

int yy[4] = {0,0,1,-1};

也许就过不了了;

因为如果用普通方法,最后得到的是最优步数,而不是最优时间;

来自Jason的解释:

普通队列+bfs确实是蒙对的,因为击败守卫需要消耗时间1,因此普通队列每一次出队列的元素只是步数上最优,但不一定是时间上最优的,这时即使我们把整个迷宫搜完以最小值作为最优依然不行,因为每一步处理完成都会把该状态标记为已处理vis[i][j]=1,因此,只要有一步不是最优,就会影响后面的结果。这题的正确做法是优先队列,每一次出队都是出时间最少的,这样可以保证每一步最优,并且一旦搜到目标即可立刻结束。

#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
char map[205][205];
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1}; 
bool visit[205][205];
int n,m;
struct point
{
	int x;
	int y;
	int step;
	friend bool operator < (point a, point b)
	{
		return a.step > b.step;
	}
}a,b;

int bfs()
{
	int flag = 0;
	memset(visit,false,sizeof(visit));
	visit[a.x][a.y] = true;
	priority_queue<point> q;
	q.push(a);
	while(!q.empty())
	{
		
		b = q.top();
		q.pop();
		if(map[b.x][b.y] == 'r')
		{
			flag = b.step;
			break;
		}	
		for(int i = 0; i < 4; i++)
		{
			a.x = b.x + xx[i];
			a.y = b.y + yy[i];
			a.step = b.step + 1;
			if(!visit[a.x][a.y]&&map[a.x][a.y]!='#')
			{
				visit[a.x][a.y] = true;
				if(map[a.x][a.y]=='x')
					a.step = a.step + 1;
				q.push(a);
			}
		}
	}
	return flag;
}
int main()
{
	while(cin>>n>>m)
	{
		for(int i=0;i<=n+1;++i)
            map[i][0]=map[i][m+1]='#';
        for(int i=0;i<=m+1;++i)
            map[0][i]=map[n+1][i]='#';
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				cin>>map[i][j];
				if(map[i][j]=='a')
				{
					a.x = i;
					a.y = j;
					a.step = 0;
				}
			}
		}
		int step = bfs();
		if(step)
		{
			cout<<step<<endl;;
		}	
		else
		{
			cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;;
		}
	}
	return 0;
	
}
/*
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
*/


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测