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
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!
题目链接
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 ;
}
