HDU

题意：一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y  ，问这个人能不能安全到达终点(且可以待在原地)
m，n，k和d（2 <= m，n <= 100,0 <= k <= 100，m + n <= d <= 1000）。 m和n是战场的大小，k是城堡的数量，d是Little A最初拥有的能量单位
思路:看当人位于某个点的时候，其四个方向是否有炮塔，这个炮塔是都向人的方向射击，然后再看子弹是否刚好位于这个坐标即可
同时用state[x][y][time]标记，对于time时刻，人位于x,y的情况只需要访问一次，这是唯一的

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int MAXN = 105;

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

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

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

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

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

queue<node>que;
int bfs()
{
    memset(vis ,0,sizeof(vis));
    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 + mov[i][0];
            tmp.y = now.y + mov[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]
               && !st[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)
    {
        memset(M, 0,sizeof(M));
        char t;
        for(int i = 0; i<k; i++)
        {
            getchar();
            scanf("%c%d%d%d%d",&t, &Castle[i].t, &Castle[i].v, &Castle[i].x, &Castle[i].y);
            if(t=='N') Castle[i].dir = 0;
            if(t=='S') Castle[i].dir = 1;
            if(t=='E') Castle[i].dir = 2;
            if(t=='W') Castle[i].dir = 3;
            M[Castle[i].x][Castle[i].y] = 1;
        }
        init();
        int ans = bfs();
        if(ans==-1)
            puts("Bad luck!");
        else
            printf("%d
", ans);
    }
}