【HDU - 3533】Escape
【HDU – 3533】Escape（bfs）
Escape
Descriptions:
一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y
问这个人能不能安全到达终点
要求:
1.人不能到达炮塔所在的坐标
2.炮塔会挡住子弹
3.途中遇到子弹是安全的，但是人如果停在这个坐标，而子弹也刚好到这个坐标，人就被射死
4.人可以选择停止不动
Input
对于每个测试用例，第一行有四个整数，m、n、k和d (2<=m, n<=100, 0<=k<=100, m+ n<=d<=1000)。m和n是战场的大小，k是城堡的数量，d是A最初拥有的能量单位。接下来的k行分别描述了这些城堡。每一行包含一个字符c和四个整数,t, v, x和y。c是“N”,“S”,“E”或“W”给城堡的发射方向,t, v是子弹的速度(即单位通过每秒),和(x, y)是城堡的位置。这里我们假设，如果一座城堡被其他城堡击中，它会挡住其他人的射击，但不会被摧毁。两颗子弹会在不影响它们的方向和速度的情况下擦肩而过。
当小A开始逃跑时，所有的城堡都开始射击。
继续到文件末尾。
Output
如果小A能逃跑，在一行中输入其所需的最小秒数。否则，在一行中输出”Bad luck!”(无需带引号)
Sample Input
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
Sample Output
9 Bad luck!
题目链接
https://vjudge.net/problem/HDU-3533
其实不难，我们只需要看当人位于某个点的时候，其四个方向是否有炮塔，这个炮塔是都向人的方向射击，然后再看子弹是否刚好位于这个坐标即可。
而标记的话，vis[x][y][time]，对于time时刻，人位于x,y的情况只需要访问一次，这是唯一的
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 105 using namespace std; int n,m,k,life; int dt[5][2] = {0,1,1,0,0,-1,-1,0,0,0};//四个方向与停止不动的走法 int map[105][105]; bool vis[105][105][1005]; struct period { char c; int t,v; } s[105][105]; struct node { int x,y,step; }; int check(int x,int y) { if(x<0 || x>n || y<0 || y>m) return 1; return 0; } void bfs() { node now,net; queue<node> q; int i,j,flag,dis,timee; now.x = now.y = now.step = 0; q.push(now); vis[0][0][0] = true; while(!q.empty()) { now = q.front(); q.pop(); if(now.step>life) break; if(now.x == n && now.y == m) { cout<<now.step<<endl; return ; } for(i = 0; i<5; i++) { net = now; net.x+=dt[i][0]; net.y+=dt[i][1]; net.step++; if(check(net.x,net.y)) continue; if(!s[net.x][net.y].t && !vis[net.x][net.y][net.step] && net.step<=life)//在符合条件的情况下，枚举四个方向 { flag = 1; for(j = net.x-1; j>=0; j--)//当位于这点，我们往北向寻找是否有朝南方向射击的炮台 { if(s[j][net.y].t && s[j][net.y].c == 'S')//找到第一个炮台，且这个炮台是朝南射击的 { dis = net.x-j;//看炮台与人的距离 if(dis%s[j][net.y].v) break;//因为不需要看子弹中途的点，子弹每一秒跑v，距离是dis，dis不能整除v的话，那么子弹是不可能停在这个点的 timee = net.step-dis/s[j][net.y].v;//人走的时间减去第一个子弹飞行到这个位置所需的时间 if(timee<0) break;//为负数就是第一个子弹都没有经过这个点，那么人绝对安全 if(timee%s[j][net.y].t==0)//看间隔，能整除，那么就是后续有子弹刚好到这个点，人死定了 { flag = 0; break; } } if(s[j][net.y].t)//找到炮台但不是朝南射击，那么这个炮台会当下后面所有子弹，所以北方向安全我们不需要再找 break; } if(!flag)//这个方向都死定了，后面也就不需要看了 continue; //其他方向也是一样的道理，就不注释了 for(j = net.x+1; j<=n; j++) { if(s[j][net.y].t && s[j][net.y].c == 'N') { dis = j-net.x; if(dis%s[j][net.y].v) break; timee = net.step-dis/s[j][net.y].v; if(timee<0) break; if(timee%s[j][net.y].t==0) { flag = 0; break; } } if(s[j][net.y].t) break; } if(!flag) continue; for(j = net.y-1; j>=0; j--) { if(s[net.x][j].t && s[net.x][j].c == 'E') { dis = net.y-j; if(dis%s[net.x][j].v) break; timee = net.step-dis/s[net.x][j].v; if(timee<0) break; if(timee%s[net.x][j].t==0) { flag = 0; break; } } if(s[net.x][j].t) break; } if(!flag) continue; for(j = net.y+1; j<=m; j++) { if(s[net.x][j].t && s[net.x][j].c == 'W') { dis = j-net.y; if(dis%s[net.x][j].v) break; timee = net.step-dis/s[net.x][j].v; if(timee<0) break; if(timee%s[net.x][j].t==0) { flag = 0; break; } } if(s[net.x][j].t) break; } if(!flag) continue; vis[net.x][net.y][net.step] = true; q.push(net); } } } cout<<"Bad luck!"<<endl; } int main() { while(cin>>n>>m>>k>>life) { MEM(vis,0); MEM(s,0); for(int i=0; i<k; i++) { char c; int t,v,x,y; cin>>c>>t>>v>>x>>y; s[x][y].c=c; s[x][y].t=t; s[x][y].v=v; } bfs(); } return 0; }
版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。