这是一道广搜的题，起点终点是明确的，最后求逃离迷宫的最短步数，所以是比较原始的广度优先搜索。

处理的难点在于哪些点是不能访问的，即，所谓的障碍物。

由于多了一个时间的维度，所以，记录迷宫的图、标记访问状态的数组，都将是三维的boolean数组。

g[x][y][t] 表示点 (x, y) 在时刻 t 可以踩上去，visited[x][y][t] 记录三元组的访问状态。

队列中存放的访问信息就是 (x, y, t) 的三元组。

由于有生命的限制，所以数组的第三个维度开到 d 就可以了，在广搜的任何一个时刻只要 t > d 就立刻结束搜索。

难点在于哪些点是不可访问的。

守卫站着的点是永远不能访问的。

只需要预处理所有子弹会出现的点、以及时刻。

计算子弹在给定方向上的所有可能出现的位置以及出现的时刻，标记所有这些 (x, y, p) 三元组不可访问。

然后在 p < d 的前提下每次将 p 增加子弹射击的间隔 t。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static boolean[][][] g; // 点 (x, y) 在时刻 t 是否可达
	static boolean[][][] visited; // 标记访问状态
	static int n;
	static int m;
	static int d;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		int k = in.nextInt();
		d = in.nextInt();
		g = new boolean[n + 1][m + 1][d + 1];
		visited = new boolean[n + 1][m + 1][d + 1];
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m ;j++)
				for (int l = 0; l <= d; l++)
					g[i][j][l] = true; // 默认都可以访问
		for (int i = 0; i < k; i++) {
			String c = in.next();
			int t = in.nextInt();
			int v = in.nextInt();
			int x = in.nextInt();
			int y = in.nextInt();
			// 守卫所在的点永远不可达
			for (int j = 0; j <= d; j++) {
				g[x][y][j] = false;
			}
			// 获取射击方向
			int dx = 0, dy = 0;
			switch (c) {
			case "N":
				dx = -1;
				break;
			case "S":
				dx = 1;
				break;
			case "W":
				dy = -1;
				break;
			case "E":
				dy = 1;
				break;
			}
			int p = 1;
			// 计算子弹到达的点及到达的时间，在该时刻该点不可达
			while (p <= d) {
				int newX = x + dx * v * p;
				int newY = y + dy * v * p;
				// 计算第一颗子弹命中的位置
				if (newX >=0 && newX <= n && newY >=0 && newY <= m) {
					g[newX][newY][p] = false;
					int l = 1;
					while (p + l * t <= d) {
						// 该位置每隔 t 秒命中一次
						g[newX][newY][p + l * t] = false;
						l++;
					}
				}
				p++;
			}
		}
		// 预处理完成，开始广搜，输出答案
		int ans = bfs(0, 0, 0);
		System.out.println(ans == -1 ? "Bad luck!" : ans);
		in.close();
	}

	private static int bfs(int X, int Y, int T) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(X, Y, T));
		visited[X][Y][T] = true;
		while (!q.isEmpty()) {
			Point current = q.poll();
			// 在生命耗尽之前到达出口
			if (current.getX() == n && current.getY() == m && current.getT() <= d) {
				return current.getT();
			} else if (current.getT() > d){
				// 耗时大于生命，直接死掉
				return -1;
			} else {
				for (Point neighbour : getNeighbours(current)) {
					visited[neighbour.getX()][neighbour.getY()][neighbour.getT()] = true;
					q.add(neighbour);
				}
			}
		}
		// 走投无路，死掉
		return -1;
	}
	
	private static ArrayList<Point> getNeighbours(Point p) {
		ArrayList<Point> neighbours = new ArrayList<Point>();
		int x = p.getX();
		int y = p.getY();
		int t = p.getT();
		for (int dx = -1; dx <= 1; dx++)
			for (int dy = -1; dy <= 1; dy++) {
				// 可以站在原地等 1 秒，找子弹的空隙，所以一共是 5 个邻居
				if (Math.abs(dx) != Math.abs(dy) || dx == 0 && dy == 0) {
					int xx = x + dx;
					int yy = y + dy;
					// t + 1 > d 的全部剪枝
					if (xx >= 0 && xx <= n && yy >= 0 && yy <= m && t + 1 <= d) {
						if (g[xx][yy][t + 1])
							if (!visited[xx][yy][t + 1])
							neighbours.add(new Point(xx, yy, t + 1));
					}
				}
			}
		return neighbours;
	}
}

class Point {
	private int x;
	private int y;
	private int t;
	
	public Point(int x, int y, int t) {
		super();
		this.x = x;
		this.y = y;
		this.t = t;
	}
	
	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getT() {
		return t;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + t;
		result = prime * result + x;
		result = prime * result + y;
		return result;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Point other = (Point) obj;
		if (t != other.t)
			return false;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}
	
	@Override
	public String toString() {
		return "Point [x=" + x + ", y=" + y + ", t=" + t + "]";
	}
	
}