$$\color{Purple}{kuangbin题解目录}$$
描述
一个 $m \\times n$ 大小的长方形战场如下所示。
一个士兵需要从 $(0,0)$ 出发前往 $(m,n)$。
为了不延误战机,他在路上花费的时间不能超过 $d$ 秒。
战场上有 $k$ 个防御塔,每个防御塔都会周期性的朝某个固定方向不断发射炮弹。
如果士兵不能在规定时限内抵达目的地,或者在行动过程中被炮弹击中,那么他的任务就失败了。
已知,他每秒可以沿东南西北任一方向移动 $1$ 个单位距离。也可以为了躲避炮弹而选择原地不动。
为了让问题简化,我们规定只有士兵和炮弹在某一整数坐标位置上碰到时,士兵才会被炮弹击中。
也就是说,如果炮弹以每秒 $3$ 个单位距离的速度从 $(0,3)$ 射向 $(0,0)$,而士兵以每秒 $1$ 个单位距离的速度从 $(0,0)$ 走向 $(0,1)$,那么尽管士兵和炮弹相遇,但是由于相遇点的位置坐标不是整数,所以士兵不会被炮弹击中。
但是,如果炮弹以每秒 $2$ 个单位距离的速度从 $(0,3)$ 射向 $(0,0)$,而士兵以每秒 $1$ 个单位距离的速度从 $(0,0)$ 走向 $(0,1)$,那么 $1$ 秒后士兵和炮弹恰好在 $(0,1)$ 相遇,士兵被炮弹击中。
给定战场的具体情况,请你判断士兵是否能够完成任务。
输入格式
输入包含多组测试数据。
每组数据第一行包含四个整数 $m,n,k,d$。
接下来 $k$ 行,每行首先包含一个大写字母(N
,S
,E
,W
之一),表示一个防御塔的炮弹发射朝向,然后包含四个整数 $t,v,x,y$,分别表示炮弹的发射周期,飞行速度,以及防御塔的位置横纵坐标。
炮弹之间不会发生碰撞,炮弹会被防御塔阻拦,所有防御塔在第 $0$ 秒发射第一发炮弹。
士兵不能走到防御塔所在的位置。
输出格式
每组数据输出一行结果,如果可以士兵可以完成任务,则输出所需最短时间,否则输出 Bad luck!
。
数据范围
$2 \\le m,n \\le 100$,
$0 \\le k \\le 100$,
$m + n \\le d \\le 1000$。
保证防御塔不会位于 $(0,0)$ 或 $(m,n)$,并且两两位置不同。
输入样例:
4 4 3 10
N 1 1 1 1
W 1 1 3 2
W 2 1 2 4
4 4 3 10
N 1 1 1 1
W 1 1 3 2
W 1 1 2 4
输出样例:
9
Bad luck!
思路
- 利用
bfs
解决该题即可.- 首先,考虑每个防御塔在最大花费时间内,每个炮弹的着落位置(运动方向、运动距离),每个周期内对其坐标的影响;
- 其次,每个炮弹不能遇到防御塔(防御塔可看作是座墙);
- 前半部分先
预处理
炮弹的情况,后半部分就是用bfs
处理人的具体运动状态(注意此题该人可以原地不动躲避炮弹);- 最后,考虑该人的运动状态(该点合法、不在防御塔位置、当前时刻炮弹打不过来、当前位置的这个时刻未访问过).
- 注意
剪枝
,若当前时刻已经大于最大花费时间时,不用再跑bfs
了
代码
注意queue
放结构体建议先存着,不建议写成q.push{..,..,...}
,被卡$tle$了,详细见代码
// Problem: 逃跑
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4233/
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// Date: 2023-01-12 15:51:08
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
using namespace std;
typedef long long ll;
struct node{
int x;
int y;
int step;
};
int m,n,k,times;//终点坐标(m,n),k防御塔个数,times花费最大时间
int dir[5][2]={{-1,0},{0,1},{1,0},{0,-1},{0,0}};//注:可原地不动(躲避炮弹)
bool having[MAXN][MAXN][1010];//标记炮弹是否在(x,y)且在当前时间存在
bool vis[MAXN][MAXN][1010];//标记人走的行为
bool g[MAXN][MAXN];//标记炮弹位置
struct bullet{
int period;//周期
int speed;//速度
int dir;//炮弹方向
int x;
int y;
}s[MAXN];
void init_bullet()
{
for(int i=1;i<=k;i++)//枚举每一座防御塔
for(int j=0;j<=times;j+=s[i].period)//模拟一枚炮弹
{
int dist=1;
while(1)//枚举距离
{
int dx=s[i].x+dir[s[i].dir][0]*dist;
int dy=s[i].y+dir[s[i].dir][1]*dist;
if(dx<0||dx>m||dy<0||dy>n||g[dx][dy]==1)//越界或被防御塔格挡
break;
if(dist%s[i].speed==0)
having[dx][dy][j+dist/s[i].speed]=1;
dist++;
}
}
}
int bfs()
{
node now,temp;
queue<node> q;
q.push({0,0,0});
vis[0][0][0]=1;
while(q.size()>0)
{
temp=q.front();
q.pop();
if(temp.step>times)//剪枝(当前的步数超过最大时间)
return -1;
if(temp.x==m&&temp.y==n)//到达终点
return temp.step;
for(int i=0;i<=4;i++)
{
now.x=temp.x+dir[i][0],now.y=temp.y+dir[i][1];
now.step=temp.step+1;
if(now.x>=0&&now.x<=m&&now.y>=0&&now.y<=n//是否越界
&&g[now.x][now.y]==0//该点不能是防御塔
&&having[now.x][now.y][now.step]==0//该点该时刻不会被炮弹打到
&&vis[now.x][now.y][now.step]==0)//该点未到达过
{
vis[now.x][now.y][now.step]=1;
//q.push({now.x,now.y,now.step});为撒这样会tle
q.push(now);//这样不会tle
}
}
}
return -1;
}
int main()
{
while(scanf("%d %d %d %d",&m,&n,&k,×)!=EOF)
{
memset(g,0,sizeof(g));
memset(having,0,sizeof(having));
memset(vis,0,sizeof(vis));
char op;
for(int i=1;i<=k;i++)
{
scanf(" %c",&op);
if(op=='N')//北-上
s[i].dir=0;
else if(op=='E')//东-右
s[i].dir=1;
else if(op=='S')//南-下
s[i].dir=2;
else if(op=='W')//西-左
s[i].dir=3;
scanf("%d %d %d %d",&s[i].period,&s[i].speed,&s[i].x,&s[i].y);
g[s[i].x][s[i].y]=1;
}
init_bullet();
int res=bfs();
if(res!=-1)
printf("%d\n",res);
else printf("Bad luck!\n");
}
return 0;
}