HDU 3533 Escape

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. 

InputFor 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. 
OutputIf 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!

题意：

第一行：m, n, k, d 分别代表m行，n列， 接下来有k组输入， d单位的时间

c, t, v, x, y 分别代表 c方位， t时间间隔， v的速度， x ：第x行， y：第y列

一个人从(0,0) 位置出发，走到(m,n)位置，途中可以停留，被炮弹打到是死，规定时间没有到达终点也是死。 这道题人的问题很简单，主要是炮弹的问题：

1， 炮弹有发射时间间隔，也就是说在规定的时间里面有可能会朝一个方向发射多枚炮弹，

2， 炮弹的速度也要关注，假如一个炮塔地点是(1,1) 朝向S方向以速度为3发射，那么人在下一时间点在(2,1) 和 (3,1) 两个点不会被打死，只有在(4,1) 这个点被打死。

3， 炮塔可以挡住炮弹，也就是说炮塔超某一方向开炮，如果此方向有炮塔，那么炮弹就会在炮塔的地方停止。

4, 本题的(x,y)要格外注意，x代表行，y代表列，与数学的二维坐标不同

思路：我们可以预先处理炮弹的在哪个时间跑到了哪个位置，我们用isb[i][j][k]表示在k时间(i,j)这个位置有一枚炮弹，所以主要就是看某一点是否有炮弹了，再处理炮弹之前，先把炮塔存一下，因为炮弹的发射受炮塔的影响。(这题是晚上睡之前看的，然后一晚上都在想有没有一个好的方法预先处理炮弹，然后最后也想到了一个方法，尽管不是很好，但是结果还算不错，第二天第一发交了一个MLE， 然后改了一下就过了。)

Status	Accepted
Time	530ms
Memory	21832kB
Length	2701
Lang	G++
Submitted	2018-01-03 11:06:12

具体请看代码分析：

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int m, n, k, d;
int dis[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool Map[101][101];        //存炮塔 
bool isb[101][101][1001];  //存炮弹
bool vis[101][101][1001];  //标记，某一时间某一地点是否已经经过 
struct bullet{
	char c;                //方位 
	int t, v, x, y;        //时间间隔，速度，炮塔的方位 
}s[101];
struct node{
	int x, y;
	int time;
}pre, nex;

bool MAP(int x, int y){    //边界处理 
	return x>=0 && y>=0 && x<=m && y<=n;
}
//炮弹预先处理 
void isbullet(int dx, int dy, int x, int y, int t, int v) { 
	int p;                         //代表炮弹的最大航程 
	if(dx+dy < 0)                  //代表炮弹朝坐标点减小的方向 
	p = -(dx*x+dy*y);              //最大航程 
	else                           //代表炮弹朝坐标点增大的方向 
	p = m*dx+n*dy-(dx*x + dy*y);   //最大航程 
	for(int i = 1; i < 100; i++) { //判断中途是否有炮塔 
		int bx = x + dx*i;
		int by = y + dy*i;
		if(MAP(bx, by) == 0) break;
		if(Map[bx][by] == 1) {     //找到最近的一个炮塔 
			p = i;                 //炮弹的航程更行 
			break;
		}
	}	
	for(int i = 0; i*t <= d; i++) {      //代表时间，t为时间间隔 
		for(int j = 1; j <= p/v; j++) {  //p/v代表炮弹的点， 
			int bx = j*v*dx + x;         //假如p=10， v=3， 那么炮弹在这段时间里，只会有三个点人不能走 
			int by = j*v*dy + y;
			if(MAP(bx, by) == 0) break; 
			int time = i*t + j;          //炮弹发射后到达(bx,by)这个位置的时间 
			if(time > d) break;          //判断时间点是否"越界" 
			isb[bx][by][time] = 1;
		}
	}
}
void bfs() {
	queue<node> Q;
	pre.x = 0;
	pre.y = 0;
	pre.time = 0;
	vis[0][0][0] = 1;
	Q.push(pre);
	while(!Q.empty()) {
		nex = Q.front();
		Q.pop();
		if(nex.time > d) {             //如果大于时间就结束 
			printf("Bad luck!\n");
			return ;
		}
		if(nex.x == m && nex.y == n) { //到达终点结束 
			printf("%d\n",nex.time);
			return ;
		}
		for(int i = 0; i < 4; i++) {
			int dx = dis[i][0] + nex.x;
			int dy = dis[i][1] + nex.y;
			if(MAP(dx, dy) && Map[dx][dy] == 0) {             //判断是否有炮塔，以及是否越界 
				if(isb[dx][dy][nex.time+1]) {                 //判断下个地点下个时间是否有炮弹 
					if(isb[nex.x][nex.y][nex.time+1] == 0) {  //判断这个地点下个时间是否有炮弹 
						if(vis[nex.x][nex.y][nex.time+1] == 0) {
							pre.x = nex.x;
							pre.y = nex.y;
							pre.time = nex.time+1;
							vis[nex.x][nex.y][nex.time+1] == 1; //标记 
							Q.push(pre);							
						}
					}
				}
				if(vis[dx][dy][nex.time+1] == 0 && isb[dx][dy][nex.time+1] == 0){
					pre.x = dx;
					pre.y = dy;
					pre.time = nex.time + 1;
					vis[dx][dy][nex.time + 1] = 1;
					Q.push(pre);
				}
			}
		}
	}
	return ;
}
int main() {
	while(~scanf("%d%d%d%d",&m, &n, &k, &d)) {
		memset(vis, 0, sizeof(vis)); //初始化 
		memset(Map, 0, sizeof(Map));
		memset(isb, 0, sizeof(isb));
		for(int i = 0; i < k; i++) {
			getchar();
			scanf("%c %d %d %d %d",&s[i].c, &s[i].t, &s[i].v, &s[i].x, &s[i].y);
			Map[s[i].x][s[i].y] = 1; // 炮弹的位置置为1 
		}
		for(int i = 0; i < k; i++) {
			if(s[i].c == 'N')      isbullet(-1, 0, s[i].x, s[i].y, s[i].t, s[i].v);// 方位N 
			else if(s[i].c == 'S') isbullet( 1, 0, s[i].x, s[i].y, s[i].t, s[i].v);// 方位S
			else if(s[i].c == 'W') isbullet(0, -1, s[i].x, s[i].y, s[i].t, s[i].v);// 方位W
			else if(s[i].c == 'E') isbullet( 0, 1, s[i].x, s[i].y, s[i].t, s[i].v);// 方位E
		}
		bfs();
	}
	return 0;
}