参考：http://blog.csdn.net/libin56842/article/details/41909459
【题意】：
一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y
问这个人能不能安全到达终点
要求:
1.人不能到达炮塔所在的坐标
2.炮塔会挡住子弹
3.途中遇到子弹是安全的，但是人如果停在这个坐标，而子弹也刚好到这个坐标，人就被射死
4.人可以选择停止不动
思路：其实不难，我们只需要看当人位于某个点的时候，其四个方向是否有炮塔，这个炮塔是都向人的方向射击，然后再看子弹是否刚好位于这个坐标即可。
而标记的话，vis[x][y][time]，对于time时刻，人位于x,y的情况只需要访问一次，这是唯一的
【代码】
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue> using namespace std;
int m,n,k,d; bool vis[][][];
struct castle
{
int t,v;
char c;
}s[][];
struct node
{
int x,y;
int step;
node(int xx,int yy,int ss):x(xx),y(yy),step(ss){}
}; int dir[][]={{,},{-,},{,},{,-},{,}};
void Init()
{
memset(vis,,sizeof(vis));
memset(s,,sizeof(s));
}
bool check(int x,int y)
{
if(x>=&&x<=m&&y>=&&y<=n)
{
return ;
}
return ;
}
void bfs()
{
queue<node> Q;
Q.push(node(,,));
vis[][][]=;
while(!Q.empty())
{
node q=Q.front();
Q.pop();
if(q.step>d)
{
printf("Bad luck!\n");
return;
}
if(q.x==m&&q.y==n)
{
printf("%d\n",q.step);
return;
}
for(int i=;i<;i++)
{
node to=q;
to.x+=dir[i][];
to.y+=dir[i][];
to.step++;
if(!check(to.x,to.y))
{
continue;
}
if(!vis[to.step][to.x][to.y]&&!s[to.x][to.y].t)
{
int life=;
int dis;
//向北寻找 for(int k=to.x-;k>=;k--)
{
if(s[k][to.y].t)
{
if(s[k][to.y].c=='S')
{
dis=to.x-k;
if(dis%s[k][to.y].v)
{
break;
}
int tim=to.step-dis/s[k][to.y].v;
if(tim<)
{
break;
}
if(tim%s[k][to.y].t)
{
break;
}
life=;
break;
}
break;
}
}
if(life)
{
//向南
for(int k=to.x+;k<=m;k++)
{
if(s[k][to.y].t)
{
if(s[k][to.y].c=='N')
{
dis=k-to.x;
if(dis%s[k][to.y].v)
{
break;
}
int tim=to.step-dis/s[k][to.y].v;
if(tim<)
{
break;
}
if(tim%s[k][to.y].t)
{
break;
}
life=;
break;
}
break;
}
}
}
if(life)
{
//向东
for(int k=to.y+;k<=n;k++)
{
if(s[to.x][k].t)
{
if(s[to.x][k].c=='W')
{
dis=k-to.y;
if(dis%s[to.x][k].v)
{
break;
}
int tim=to.step-dis/s[to.x][k].v;
if(tim<)
{
break;
}
if(tim%s[to.x][k].t)
{
break;
}
life=;
break;
}
break;
}
}
}
if(life)
{
//向西
for(int k=to.y-;k>=;k--)
{
if(s[to.x][k].t)
{
if(s[to.x][k].c=='E')
{
dis=to.y-k;
if(dis%s[to.x][k].v)
{
break;
}
int tim=to.step-dis/s[to.x][k].v;
if(tim<)
{
break;
}
if(tim%s[to.x][k].t)
{
break;
}
life=;
break;
}
break;
}
}
}
if(life)
{
vis[to.step][to.x][to.y]=;
Q.push(to);
} } }
} }
int main()
{
while(~scanf("%d%d%d%d",&m,&n,&k,&d))
{
Init(); for(int i=;i<k;i++)
{
char c[];
int t,v,x,y;
scanf("%s%d%d%d%d",c,&t,&v,&x,&y);
s[x][y].c=c[];
s[x][y].t=t;
s[x][y].v=v;
}
bfs();
}
return ;
}
BFS
【教训】
开始的时候是MLE，仔细查看了很久才反应过来，int vis[1005][105][105]数组开大了，1005*105*105/4/1000=44320kb,超出了题目限制32768kb,于是把int改成bool就A了。用sizeof操作符可以查看int占用4个字节，bool占用1个字节。以前做题从来不在意，都混着用.....以后还是要注意点....