问题描述
蒜头被困在了一个 n+1 行 m+1 列的迷宫当中，蒜头所在位置为左上角的 (0,0)，他需要逃跑到位于右下角(n,m) 的出口位置。在逃跑的过程中，蒜头只可以向东南西北四个方向移动，当然也可以选择停留在某一位置，他每移动一个单位距离需要 1 秒的时间，蒜头初始时刻的能量为d，蒜头在迷宫当中每过 1 秒需要消耗 1 单位能量。在迷宫中有 k 个士兵，他们会朝着某一方向周期性地射击，子弹只会在整点位置射中蒜头。当蒜头被子弹射中、和士兵相遇或者能量消耗完时，他将死去。求蒜头逃离迷宫的最短时间。
输入格式
第一行包含四个整数n,m,k,d(2≤n,m≤100;0≤k≤100;m+n≤d≤1000)。
接下来 k 行每行包含一个字符 c 和四个整数 t,v,x,y(t,v≤100;0≤x≤n;0≤y≤m)，其中 c 表示每个士兵的射击方向，使用N、S、W、E表示上下左右四个方向，射击的周期为 t，子弹的速度为 v，士兵所在位置为(x,y)。
输出格式
输出一个整数，表示蒜头逃跑的最短时间，如果蒜头不能成功的逃离迷宫，输出Bad luck!。
样例输入
4 5 3 10
N 1 1 1 1
W 1 1 3 2
W 2 1 2 4
样例输出
10
不带了打了直接copy一份现成的慢慢研究：传送门
他写了DFS，BFS两个版本的，但BFS有bug，于是我就放了DFS的
AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
//some
int ans = 2000;
int n, m, k, d; // k->soldier d->energy
char dirx, mapp[maxn][maxn];
bool vis[2000][maxn][maxn];
int t, v, x, y; // T v (x, y)
int dir[5][2] = { //direction
{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
//dfs
void dfs(int x, int y, int t){
if(t > d || t > ans) return; // 剪枝
if(x == n && y == m) { // 到达终点
if(ans > t){ //记录最小解
ans = t;
}
return;
}
vis[t][x][y] = true;
for(int i = 0; i < 5; i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(tx < 0 || tx > n || ty < 0 || ty > m) // 越界
continue;
if(vis[t+1][tx][ty] == false && mapp[tx][ty] != '#'){
dfs(tx, ty, t+1);
}
}
vis[t][x][y] == false;
}
//sign
void signvis(int k){
for(int i = 0; i < k; i++){
cin >> dirx >> t >> v >> x >> y;
mapp[x][y] = '#';
if(dirx == 'N'){
int col_num = x; // (x,y)N方向有几行
int val_num = (col_num / v); //发送后整点到达的点位置的个数
if(val_num > 0){
for(int a = 0; a <= d; a += t){
for(int b = 1; b <= val_num; b++){
int xx = x - b*v;
vis[a+b][xx][y] = true;
}
}
}
}
else if(dirx == 'S'){
int col_num = n - x;
int val_num = (col_num / v);
if(val_num > 0){
for(int a = 0; a <= d; a += t){
for(int b = 1; b <= val_num; b++){
int xx = x + b*v;
vis[a+b][xx][y] = true;
}
}
}
}
else if(dirx == 'W'){
int row_num = y;
int val_num = (row_num / v);
if(val_num > 0){
for(int a = 0; a <= d; a += t){
for(int b = 1; b <= val_num; b++){
int yy = y - b*v;
vis[a+b][x][yy] = true;
}
}
}
}
else {
int row_num = m - y;
int val_num = (row_num / v);
if(val_num > 0){
for(int a = 0; a <= d; a += t){
for(int b = 1; b <= val_num; b++){
int yy = y + b*v;
vis[a+b][x][yy] = true;
}
}
}
}
}
}
//main()
int main() {
memset(vis, false, sizeof(vis));
memset(mapp, '.', sizeof(mapp));
cin >> n >> m >> k >> d;
if(k != 0){
signvis(k);
}
dfs(0,0,0);
if(ans > d)
cout << "Bad luck!" << endl;
else
cout << ans << endl;
return 0;
}