Escape （HDU - 3533，BFS + 模拟）
一.题目链接：
HDU-3533
二.题目大意：
第一行 4 个整数 m，n，k，d.
m × n 是地图大小，有 k 个炮塔.
d 是初始生命值，每秒消耗 1 点生命值.
之后 k 行.
每行有 ch，t，v，x，y.
ch = {'N', 'S', 'W', 'E'}
t 为该炮塔发射炮弹的间隔时间.
v 为该炮台发射子弹的速度.
x，y 为该炮台的坐标.
A 的初始位置在 (0, 0)，出口在 (m, n).
若 A 生命值为 0 或 被子弹打中，则 A 死亡.
ps：炮台可挡住其他子弹.
三.分析：
直接 BFS + 模拟...
详见代码.
四.代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e2;
const int inf = 0x3f3f3f;
struct node1
{
char ch;
int t;
int v;
} castle[M + 5][M + 5];
struct node2
{
int x;
int y;
int step;
};
bool vis[M * 10 + 5][M + 5][M + 5];
int Move[5][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
int bfs(int m, int n, int d)
{
struct node2 p, t;
p.x = p.y = p.step = 0;
vis[0][0][0] = 1;
queue <node2> q;
q.push(p);
while(!q.empty())
{
p = q.front();
q.pop();
if(p.x == m && p.y == n)
return p.step;
for(int i = 0; i < 5; ++i)
{
t = p;
t.x += Move[i][0];
t.y += Move[i][1];
t.step++;
if(t.x < 0 || t.x > m || t.y < 0 || t.y > n)
continue;
if(!castle[t.x][t.y].t && !vis[t.step][t.x][t.y] && t.step <= d)
{
bool flag = 1;
for(int j = t.x - 1; j >= 0; --j)///查找上方的炮台
{
if(castle[j][t.y].v && castle[j][t.y].ch == 'S')///炮台在上方 且 向下方发射子弹
{
int dis = t.x - j;
if(dis % castle[j][t.y].v)///若所在位置无法被子弹速度整除
break;
int times = t.step - dis / castle[j][t.y].v;///已用时间 - 子弹从出点到达此点的时间
if(times % castle[j][t.y].t == 0)
{
flag = 0;
break;
}
}
else if(castle[j][t.y].v && castle[j][t.y].ch != 'S')///帮 A 挡住子弹
break;
}
if(!flag)
continue;
for(int j = t.x + 1; j <= m; ++j)
{
if(castle[j][t.y].v && castle[j][t.y].ch == 'N')
{
int dis = j - t.x;
if(dis % castle[j][t.y].v)
break;
int times = t.step - dis / castle[j][t.y].v;
if(times % castle[j][t.y].t == 0)
{
flag = 0;
break;
}
}
else if(castle[j][t.y].v && castle[j][t.y].ch != 'N')
break;
}
if(!flag)
continue;
for(int j = t.y - 1; j >= 0; --j)
{
if(castle[t.x][j].v && castle[t.x][j].ch == 'E')
{
int dis = t.y - j;
if(dis % castle[t.x][j].v)
break;
int times = t.step - dis / castle[t.x][j].v;
if(times % castle[t.x][j].t == 0)
{
flag = 0;
break;
}
}
else if(castle[t.x][j].v && castle[t.x][j].ch != 'E')
break;
}
if(!flag)
continue;
for(int j = t.y + 1; j <= n; ++j)
{
if(castle[t.x][j].v && castle[t.x][j].ch == 'W')
{
int dis = j - t.y;
if(dis % castle[t.x][j].v)
break;
int times = t.step - dis / castle[t.x][j].v;
if(times % castle[t.x][j].t == 0)
{
flag = 0;
break;
}
}
else if(castle[t.x][j].v && castle[t.x][j].ch != 'W')
break;
}
if(!flag)
continue;
vis[t.step][t.x][t.y] = 1;
q.push(t);
}
}
}
return -1;
}
void init(int m, int n)
{
for(int i = 0; i <= M * 10; ++i)
{
for(int j = 0; j <= m; ++j)
{
for(int k = 0; k <= n; ++k)
{
vis[i][j][k] = 0;
castle[j][k].t = castle[j][k].v = 0;
}
}
}
}
int main()
{
int m, n, k, d;
while(~scanf("%d %d %d %d", &m, &n, &k, &d))
{
init(m, n);
char ch;
int t, v, x, y;
for(int i = 0; i < k; ++i)
{
getchar();
scanf("%c %d %d %d %d", &ch, &t, &v, &x, &y);
castle[x][y].ch = ch;
castle[x][y].t = t;
castle[x][y].v = v;
}
int ans = bfs(m, n, d);
if(~ans)
printf("%d\n", ans);
else
printf("Bad luck!\n");
}
return 0;
}
查看3道真题和解析