HDU3533 Escape —— BFS / A*算法 + 预处理

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3533

Escape

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1792    Accepted Submission(s): 529

Problem Description

The students of the HEU are maneuvering for their military training.
The red army and the blue army are at war today. The blue army finds that Little A is the spy of the red army, so Little A has to escape from the headquarters of the blue army to that of the red army. The battle field is a rectangle of size m*n, and the headquarters of the blue army and the red army are placed at (0, 0) and (m, n), respectively, which means that Little A will go from (0, 0) to (m, n). The picture below denotes the shape of the battle field and the notation of directions that we will use later.



The blue army is eager to revenge, so it tries its best to kill Little A during his escape. The blue army places many castles, which will shoot to a fixed direction periodically. It costs Little A one unit of energy per second, whether he moves or not. If he uses up all his energy or gets shot at sometime, then he fails. Little A can move north, south, east or west, one unit per second. Note he may stay at times in order not to be shot.
To simplify the problem, let’s assume that Little A cannot stop in the middle of a second. He will neither get shot nor block the bullet during his move, which means that a bullet can only kill Little A at positions with integer coordinates. Consider the example below. The bullet moves from (0, 3) to (0, 0) at the speed of 3 units per second, and Little A moves from (0, 0) to (0, 1) at the speed of 1 unit per second. Then Little A is not killed. But if the bullet moves 2 units per second in the above example, Little A will be killed at (0, 1).
Now, please tell Little A whether he can escape.

 

Input

For every test case, the first line has four integers, m, n, k and d (2<=m, n<=100, 0<=k<=100, m+ n<=d<=1000). m and n are the size of the battle ground, k is the number of castles and d is the units of energy Little A initially has. The next k lines describe the castles each. Each line contains a character c and four integers, t, v, x and y. Here c is ‘N’, ‘S’, ‘E’ or ‘W’ giving the direction to which the castle shoots, t is the period, v is the velocity of the bullets shot (i.e. units passed per second), and (x, y) is the location of the castle. Here we suppose that if a castle is shot by other castles, it will block others’ shots but will NOT be destroyed. And two bullets will pass each other without affecting their directions and velocities.
All castles begin to shoot when Little A starts to escape.
Proceed to the end of file.

 

Output

If Little A can escape, print the minimum time required in seconds on a single line. Otherwise print “Bad luck!” without quotes.

 

Sample Input

4 4 3 10 N 1 1 1 1 W 1 1 3 2 W 2 1 2 4 4 4 3 10 N 1 1 1 1 W 1 1 3 2 W 1 1 2 4

 

Sample Output

9 Bad luck!

 

Source

2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU

题解：
题目要求：

1.直接把能量限制当成时间限制吧，在规定的时间内，从左上角到达右下角。

2.人可以上下左右走或不走， 每座城堡都有一支方向固定的枪，每支枪都有规定的速度和发射频率。

3.人只有在整数时刻下与子弹相遇才会被命中。

4.如果一座城堡被其他子弹射中，那颗子弹会被挡***意：即使不是在整数时刻射中，子弹也会被挡下。

做法：

1.开一个三维数组 hav[x][y][time]，表明在time时刻， 坐标(x,y)上有无子弹。显然需要预处理这个数组。

2.使用BFS或者A*搜索

3.关于判重：一开始想到，由于子弹的进程是动态的，所以人可能为了回避子弹而往回走，所以就没有加vis判重（当初想到的是vis[x][y]的二维判重）。结果当然是不能通过了，后来看了下题解，开了个三维判重：vis[x][y][time]，即增加了"时刻"这一维度。

问：那平常的的为什么开二维判重（vis[x][y]）就够了呢，如POJ1077 八数码？

答：因为平常的题目，不用往回走。当第一次被访问的时候，这个位置被访问的最早时间一定是当前时间，之后的访问时间都不可能小于它，这个最早时间对于题目来说是最优 的，所以不用加上“时间”维度。而此题可以往回走，有可能出现最早时刻到达了这个位置，而下一时刻不管怎么走，都会被射死，反而是第二早访问时间才可以逃过一劫。因此这个最早访问时间对于题目来说不一定是最优的，所以此题要加上“时间”维度来判重。

BFS：

Accepted

3533

764MS

25768K

2698 B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 100+10;

bool M[MAXN][MAXN], hav[MAXN][MAXN][1010];
bool vis[MAXN][MAXN][1010];

int dir[5][2] = {-1,0, 1,0, 0,1, 0,-1,0 ,0};
int n, m, k, d;

struct
{
    int dir, x, y, t,v;
}ca[MAXN];

struct node
{
    int x, y, step;
};

void pre_set()
{
    ms(hav, 0);
    for(int i = 0; i<k; i++)    //枚举城堡
    {
        for(int j = 0; j<=d; j += ca[i].t)    //模拟一颗子弹
        {
            for(int k = 1; ; k++)   //枚举路程
            {
                int x = ca[i].x + dir[ca[i].dir][0]*k;
                int y = ca[i].y + dir[ca[i].dir][1]*k;
                if(x<0 || x>n || y<0 ||y>m || M[x][y]) break;
                if(k%ca[i].v==0)    //到达整点时刻，更新hav数组
                    hav[x][y][j+k/ca[i].v] = true;
            }
        }
    }
}

queue<node>que;
int bfs()
{
    ms(vis ,0);
    while(!que.empty()) que.pop();

    node now, tmp;
    now.x = now.y = 0;
    now.step = 0;
    vis[0][0][0] = true;
    que.push(now);

    while(!que.empty())
    {
        now = que.front();
        que.pop();

        if(now.step>d)  //累死了
            return -1;
        if(now.x==n && now.y==m)    //顺利回营
            return now.step;

        for(int i = 0; i<5; i++)
        {
            tmp.x = now.x + dir[i][0];
            tmp.y = now.y + dir[i][1];
            tmp.step = now.step + 1;
            if(tmp.x>=0 && tmp.x<=n && tmp.y>=0 && tmp.y<=m && !M[tmp.x][tmp.y]
               && !hav[tmp.x][tmp.y][tmp.step] && !vis[tmp.x][tmp.y][tmp.step])
            {
                vis[tmp.x][tmp.y][tmp.step] = 1;
                que.push(tmp);
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d%d%d",&n,&m,&k,&d)!=EOF)
    {
        ms(M, 0);
        char dir;
        for(int i = 0; i<k; i++)
        {
            getchar();
            scanf("%c%d%d%d%d",&dir, &ca[i].t, &ca[i].v, &ca[i].x, &ca[i].y);
            if(dir=='N') ca[i].dir = 0;
            if(dir=='S') ca[i].dir = 1;
            if(dir=='E') ca[i].dir = 2;
            if(dir=='W') ca[i].dir = 3;
            M[ca[i].x][ca[i].y] = 1;
        }

        pre_set();
        int ans = bfs();
        if(ans==-1)
            puts("Bad luck!");
        else
            printf("%d\n", ans);
    }
}

A*：

Accepted

3533

374MS

26092K

2861 B

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 100+10;

bool M[MAXN][MAXN], hav[MAXN][MAXN][1010];
bool vis[MAXN][MAXN][1010];

int dir[5][2] = {-1,0, 1,0, 0,1, 0,-1,0 ,0};
int n, m, k, d;

struct
{
    int dir, x, y, t,v;
}ca[MAXN];

struct node
{
    int x, y, f, g, h;  //g即为step
    bool operator<(const node &a)const{
        return f>a.f;
    }
};

void pre_set()
{
    ms(hav, 0);
    for(int i = 0; i<k; i++)    //枚举城堡
    {
        for(int j = 0; j<=d; j += ca[i].t)    //模拟一颗子弹
        {
            for(int k = 1; ; k++)   //枚举路程
            {
                int x = ca[i].x + dir[ca[i].dir][0]*k;
                int y = ca[i].y + dir[ca[i].dir][1]*k;
                if(x<0 || x>n || y<0 ||y>m || M[x][y]) break;
                if(k%ca[i].v==0)    //到达整点时刻，更新hav数组
                    hav[x][y][j+k/ca[i].v] = true;
            }
        }
    }
}

priority_queue<node>que;
int bfs()
{
    ms(vis ,0);
    while(!que.empty()) que.pop();

    node now, tmp;
    now.x = now.y = 0;
    now.g = 0;
    vis[0][0][0] = true;
    que.push(now);

    while(!que.empty())
    {
        now = que.top();
        que.pop();

        if(now.g>d) //累死了
            return -1;
        if(now.x==n && now.y==m)    //顺利回营
            return now.g;

        for(int i = 0; i<5; i++)
        {
            tmp.x = now.x + dir[i][0];
            tmp.y = now.y + dir[i][1];
            tmp.g = now.g + 1;
            if(tmp.x>=0 && tmp.x<=n && tmp.y>=0 && tmp.y<=m && !M[tmp.x][tmp.y]
               && !hav[tmp.x][tmp.y][tmp.g] && !vis[tmp.x][tmp.y][tmp.g])
            {
                vis[tmp.x][tmp.y][tmp.g] = 1;
                tmp.h = abs(tmp.x-n) + abs(tmp.y-m);
                tmp.f = tmp.g + tmp.h;
                que.push(tmp);
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d%d%d",&n,&m,&k,&d)!=EOF)
    {
        ms(M, 0);
        char dir;
        for(int i = 0; i<k; i++)
        {
            getchar();
            scanf("%c%d%d%d%d",&dir, &ca[i].t, &ca[i].v, &ca[i].x, &ca[i].y);
            if(dir=='N') ca[i].dir = 0;
            if(dir=='S') ca[i].dir = 1;
            if(dir=='E') ca[i].dir = 2;
            if(dir=='W') ca[i].dir = 3;
            M[ca[i].x][ca[i].y] = 1;
        }

        pre_set();
        int ans = bfs();
        if(ans==-1)
            puts("Bad luck!");
        else
            printf("%d\n", ans);
    }
}