题意：一个人从(0, 0)逃往(n, m)，地图上有朝某个方向开炮的炮台，问最少逃脱步数
分析：主要在状态是否OK，当t时刻走到(x，y)，炮台是否刚好打中，因为只能是整数，所以用整除判断。题意不清楚，有些坑点。
#include <bits/stdc++.h>
using namespace std; const int N = 1e2 + 5;
struct Point {
int dir, t, v; //N 1 E 2 S 3 W 4
}p[N][N];
struct Node {
int x, y, step;
Node() {}
Node(int x, int y, int step) : x (x), y (y), step (step) {}
};
int dx[5] = {-1, 1, 0, 0, 0};
int dy[5] = {0, 0, -1, 1, 0};
bool vis[N][N][N*10];
int n, m, k, d; bool check(int x, int y, int tim) {
if (x < 0 || x > n || y < 0 || y > m || vis[x][y][tim] || p[x][y].dir != 0) return false;
else return true;
} bool check2(int x, int y, int tim) {
for (int i=x-1; i>=0; --i) { //up
if (p[i][y].v == 0) continue;
if (p[i][y].dir != 3) break;
int dis = x - i;
if (dis % p[i][y].v != 0) break;
int t = tim - dis / p[i][y].v;
if (t % p[i][y].t == 0) return false;
else break;
}
for (int i=x+1; i<=n; ++i) { //down
if (p[i][y].v == 0) continue;
if (p[i][y].dir != 1) break;
int dis = i - x;
if (dis % p[i][y].v != 0) break;
int t = tim - dis / p[i][y].v;
if (t % p[i][y].t == 0) return false;
else break;
}
for (int i=y-1; i>=0; --i) { //left
if (p[x][i].v == 0) continue;
if (p[x][i].dir != 2) break;
int dis = y - i;
if (dis % p[x][i].v != 0) break;
int t = tim - dis / p[x][i].v;
if (t % p[x][i].t == 0) return false;
else break;
}
for (int i=y+1; i<=m; ++i) { //right
if (p[x][i].v == 0) continue;
if (p[x][i].dir != 4) break;
int dis = i - y;
if (dis % p[x][i].v != 0) break;
int t = tim - dis / p[x][i].v;
if (t % p[x][i].t == 0) return false;
else break;
} return true;
} int BFS(void) {
Node s;
s.x = s.y = s.step = 0;
queue<Node> que; que.push (s);
vis[s.x][s.y][0] = true;
while (!que.empty ()) {
Node u = que.front (); que.pop ();
if (u.step > d) continue;
if (u.x == n && u.y == m && u.step <= d) {
return u.step;
}
for (int i=0; i<5; ++i) {
int tx = u.x + dx[i], ty = u.y + dy[i], tsp = u.step + 1;
if (!check (tx, ty, tsp)) continue;
if (!check2 (tx, ty, tsp)) continue;
vis[tx][ty][tsp] = true;
que.push (Node (tx, ty, tsp));
}
} return -1;
} int main(void) {
map<char, int> mp;
mp['N'] = 1; mp['E'] = 2; mp['S'] = 3; mp['W'] = 4;
while (scanf ("%d%d%d%d", &n, &m, &k, &d) == 4) {
memset (vis, false, sizeof (vis));
memset (p, 0, sizeof (p));
char str[3]; int t, v, x, y;
getchar ();
for (int i=0; i<k; ++i) {
scanf ("%s%d%d%d%d", &str, &t, &v, &x, &y);
p[x][y].dir = mp[str[0]];
p[x][y].t = t; p[x][y].v = v;
}
int ans = BFS ();
if (ans == -1) puts ("Bad luck!");
else printf ("%d\n", ans);
} return 0;
}