HDU 3533
题意：
一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y
问这个人能不能安全到达终点
要求:
1.人不能到达炮塔所在的坐标
2.炮塔会挡住子弹
3.途中遇到子弹是安全的，但是人如果停在这个坐标，而子弹也刚好到这个坐标，人就被射死
4.人可以选择停止不动
思路：其实不难，我们只需要看当人位于某个点的时候，其四个方向是否有炮塔，这个炮塔是都向人的方向射击，然后再看子弹是否刚好位于这个坐标即可。
而标记的话，vis[x][y][time]，对于time时刻，人位于x,y的情况只需要访问一次，这是唯一的
参考别人的做的，差点T了，注意题目上说简化题意没有 静止不动的情况，但若考虑会wa。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
int n,m,k,d;
int map[110][110];
struct castle
{
int x,y,v,t;
int fx;
}pao[110];
bool vis[110][110][1100];
struct node
{
int x,y,step;
};
int dir[5][2]={ 1,0, -1,0, 0,1, 0,-1, 0, 0};
void bfs()
{
memset(vis,0,sizeof(vis));
struct node u,v;
u.x=0; u.y=0; u.step=0;
vis[0][0][0]=1;
queue<node> que ;
que.push(u);
while(!que.empty())
{
u=que.front() ; que.pop();
if(u.x==n&&u.y==m)
{
if(u.step<=d) printf("%d\n",u.step);
else printf("Bad luck!\n");
return;
}
for(int i=0;i<5;++i)
{
int xx=u.x+dir[i][0],yy=u.y+dir[i][1];
if(xx<0||yy<0||xx>n||yy>m) continue;
if(vis[xx][yy][u.step+1]==1||map[xx][yy]!=-1) continue ;
bool flag=1;
for(int j=xx+1;j<=n;++j)
{
if(map[j][yy]!=-1)
{
int id = map[j][yy];
int much = j-xx;
int time= u.step+1-(much/pao[id].v);
if(pao[id].fx!=1||much%pao[id].v) break;
if(time<0) break;
if(time%pao[id].t==0) { flag =0; break;}
}
}
if(flag==0) continue;
for(int j=xx-1;j>=0;--j)
{
if(map[j][yy]!=-1)
{
int id = map[j][yy];
int much = xx-j;
int time= u.step+1-(much/pao[id].v);
if(pao[id].fx!=3||much%pao[id].v) break;
if(time<0) break;
if(time%pao[id].t==0) { flag =0; break;}
}
}
if(flag==0) continue;
for(int j=yy+1;j<=m;++j)
{
if(map[xx][j]!=-1)
{
int id = map[xx][j];
int much = j-yy;
int time= u.step+1-(much/pao[id].v);
if(pao[id].fx!=4||much%pao[id].v) break;
if(time<0) break;
if(time%pao[id].t==0) { flag =0; break;}
}
}
if(flag==0) continue;
for(int j=yy-1;j>=0;--j)
{
if(map[xx][j]!=-1)
{
int id = map[xx][j];
int much = yy-j;
int time= u.step+1-(much/pao[id].v);
if(pao[id].fx!=2||much%pao[id].v) break;
if(time<0) break;
if(time%pao[id].t==0) { flag =0; break;}
}
}
if(flag==0) continue;
v.x=xx; v.y=yy; v.step=u.step+1; vis[xx][yy][u.step+1]=1;
que.push(v);
}
}
printf("Bad luck!\n");
return ;
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&k,&d)!=EOF)
{
char s[5];
int t,v,x,y,temp;
memset(map,-1,sizeof(map));
for(int i=1;i<=k;++i)
{
scanf("%s",s);
scanf("%d%d%d%d",&t,&v,&x,&y);
if(s[0]=='N') temp = 1;
else if(s[0]=='E') temp = 2;
else if(s[0]=='S') temp = 3;
else temp = 4;
pao[i].fx=temp; pao[i].x=x; pao[i].y=y; pao[i].t=t; pao[i].v=v;
map[x][y]=i;
}
bfs();
}
return 0;
}
