本文主要是介绍69-逃跑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
蒜头被困在了一个 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!。
样例输入1
4 5 3 10 N 1 1 1 1 W 1 1 3 2 W 2 1 2 4
样例输出1
10
样例输入2
4 5 3 10 N 1 1 1 1 W 1 1 3 2 W 1 1 2 4
样例输出2
Bad luck!
代码解析：
#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;
}这篇关于69-逃跑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
