Escape

Descriptions:

一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y
问这个人能不能安全到达终点
要求:
1.人不能到达炮塔所在的坐标
2.炮塔会挡住子弹
3.途中遇到子弹是安全的，但是人如果停在这个坐标，而子弹也刚好到这个坐标，人就被射死
4.人可以选择停止不动

Input

对于每个测试用例，第一行有四个整数，m、n、k和d (2<=m, n<=100, 0<=k<=100, m+ n<=d<=1000)。m和n是战场的大小，k是城堡的数量，d是A最初拥有的能量单位。接下来的k行分别描述了这些城堡。每一行包含一个字符c和四个整数,t, v, x和y。c是“N”,“S”,“E”或“W”给城堡的发射方向,t, v是子弹的速度(即单位通过每秒),和(x, y)是城堡的位置。这里我们假设，如果一座城堡被其他城堡击中，它会挡住其他人的射击，但不会被摧毁。两颗子弹会在不影响它们的方向和速度的情况下擦肩而过。

当小A开始逃跑时，所有的城堡都开始射击。

继续到文件末尾。

Output

如果小A能逃跑，在一行中输入其所需的最小秒数。否则，在一行中输出"Bad luck!"(无需带引号)

Sample Input

Sample Output

9

Bad luck!

题目链接

https://vjudge.net/problem/HDU-3533

其实不难，我们只需要看当人位于某个点的时候，其四个方向是否有炮塔，这个炮塔是都向人的方向射击，然后再看子弹是否刚好位于这个坐标即可。

而标记的话，vis[x][y][time]，对于time时刻，人位于x,y的情况只需要访问一次，这是唯一的

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 105

using namespace std;

int n,m,k,life;

int dt[][] = {,,,,,-,-,,,};//四个方向与停止不动的走法

int map[][];

bool vis[][][];

struct period

{

    char c;

    int t,v;

} s[][];

struct node

{

    int x,y,step;

};

int check(int x,int y)

{

    if(x< || x>n || y< || y>m)

        return ;

    return ;

}

void bfs()

{

    node now,net;

    queue<node> q;

    int i,j,flag,dis,timee;

    now.x = now.y = now.step = ;

    q.push(now);

    vis[][][] = true;

    while(!q.empty())

    {

        now = q.front();

        q.pop();

        if(now.step>life)

            break;

        if(now.x == n && now.y == m)

        {

            cout<<now.step<<endl;

            return ;

        }

        for(i = ; i<; i++)

        {

            net = now;

            net.x+=dt[i][];

            net.y+=dt[i][];

            net.step++;

            if(check(net.x,net.y))

                continue;

            if(!s[net.x][net.y].t && !vis[net.x][net.y][net.step] && net.step<=life)//在符合条件的情况下，枚举四个方向

            {

                flag = ;

                for(j = net.x-; j>=; j--)//当位于这点，我们往北向寻找是否有朝南方向射击的炮台

                {

                    if(s[j][net.y].t && s[j][net.y].c == 'S')//找到第一个炮台，且这个炮台是朝南射击的

                    {

                        dis = net.x-j;//看炮台与人的距离

                        if(dis%s[j][net.y].v)

                            break;//因为不需要看子弹中途的点，子弹每一秒跑v，距离是dis，dis不能整除v的话，那么子弹是不可能停在这个点的

                        timee = net.step-dis/s[j][net.y].v;//人走的时间减去第一个子弹飞行到这个位置所需的时间

                        if(timee<)

                            break;//为负数就是第一个子弹都没有经过这个点，那么人绝对安全

                        if(timee%s[j][net.y].t==)//看间隔，能整除，那么就是后续有子弹刚好到这个点，人死定了

                        {

                            flag = ;

                            break;

                        }

                    }

                    if(s[j][net.y].t)//找到炮台但不是朝南射击，那么这个炮台会当下后面所有子弹，所以北方向安全我们不需要再找

                        break;

                }

                if(!flag)//这个方向都死定了，后面也就不需要看了

                    continue;

                //其他方向也是一样的道理，就不注释了

                for(j = net.x+; j<=n; j++)

                {

                    if(s[j][net.y].t && s[j][net.y].c == 'N')

                    {

                        dis = j-net.x;

                        if(dis%s[j][net.y].v)

                            break;

                        timee = net.step-dis/s[j][net.y].v;

                        if(timee<)

                            break;

                        if(timee%s[j][net.y].t==)

                        {

                            flag = ;

                            break;

                        }

                    }

                    if(s[j][net.y].t)

                        break;

                }

                if(!flag)

                    continue;

                for(j = net.y-; j>=; j--)

                {

                    if(s[net.x][j].t && s[net.x][j].c == 'E')

                    {

                        dis = net.y-j;

                        if(dis%s[net.x][j].v)

                            break;

                        timee = net.step-dis/s[net.x][j].v;

                        if(timee<)

                            break;

                        if(timee%s[net.x][j].t==)

                        {

                            flag = ;

                            break;

                        }

                    }

                    if(s[net.x][j].t)

                        break;

                }

                if(!flag)

                    continue;

                for(j = net.y+; j<=m; j++)

                {

                    if(s[net.x][j].t && s[net.x][j].c == 'W')

                    {

                        dis = j-net.y;

                        if(dis%s[net.x][j].v)

                            break;

                        timee = net.step-dis/s[net.x][j].v;

                        if(timee<)

                            break;

                        if(timee%s[net.x][j].t==)

                        {

                            flag = ;

                            break;

                        }

                    }

                    if(s[net.x][j].t)

                        break;

                }

                if(!flag)

                    continue;

                vis[net.x][net.y][net.step] = true;

                q.push(net);

            }

        }

    }

    cout<<"Bad luck!"<<endl;

}

int main()

{

    while(cin>>n>>m>>k>>life)

    {

        MEM(vis,);

        MEM(s,);

        for(int i=; i<k; i++)

        {

            char c;

            int t,v,x,y;

            cin>>c>>t>>v>>x>>y;

            s[x][y].c=c;

            s[x][y].t=t;

            s[x][y].v=v;

        }

        bfs();

    }

    return ;

}

巴特西

【HDU - 3533】Escape（bfs）

Escape

最新文章

热门文章