广搜之逃离迷宫
程序员文章站
2023-12-23 19:58:39
...
#include <cstdio>
#include <queue>
using namespace std;
/*难在预处理子弹位置部分,不熟悉如何处理,需要多加思考多加练习。
*代码依然不是我敲的。
*/
struct node {
int x, y, deep;
node(int _x, int _y, int _deep) : x(_x), y(_y), deep(_deep) {}
};
const int kMax = 100 + 10;
const int dx[] = {-1, 1, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0};
int n, m, k, d;
bool vis[kMax * 10][kMax][kMax];
queue<node> q;
int get_direction(char ch) {
if(ch == 'N') return 0;
if(ch == 'S') return 1;
if(ch == 'W') return 2;
return 3;
}
int solve() {
while(!q.empty()) {
node t = q.front(); q.pop();
if(t.deep > d) return -1;//死了
if(t.x == n && t.y == m) return t.deep;//逃出生天
for(int i = 0;i < 5;++ i) {//尝试五个搜索出口
int x = t.x + dx[i], y = t.y + dy[i];
if(x >= 0 && x <= n && y >= 0 && y <= m &&
!vis[t.deep + 1][x][y]) {
q.push({x, y, t.deep + 1});
vis[t.deep + 1][x][y] = true;
}
}
}
return -1;
}
int main() {
char ch;
int c, t, v, x, y;
scanf("%d%d%d%d", &n, &m, &k, &d);//n+1行,m+1列,k个士兵,d个单位能量
getchar();//吃掉回车符
for(int i = 0;i < k;++ i) {
scanf("%c%d%d%d%d", &ch, &t, &v, &x, &y);
getchar();
c = get_direction(ch);//方向转化
for(int j = 0;j <= d;++ j) {//该点有士兵
vis[j][x][y] = true;
}
for(int j = 0;j < d;j += t) {//预处理每个周期所打出的子弹的落点
for(int a = 1;j + a <= d;++ a) {//计算每个子弹随时刻变化所在的地方
int tx = x + dx[c] * a * v, ty = y + dy[c] * a * v;//计算坐标
if(tx < 0 || tx > n || ty < 0 || ty > m) break;
vis[j + a][tx][ty] = true;//记录时间及坐标
}
}
}
q.push({0, 0, 0});//起点
vis[0][0][0] = true;
int res = solve();
if(res == -1) printf("Bad luck!\n");
else printf("%d\n", res);
return 0;
}