題意：有一個人要從(0，0)走到（n，m），圖中有k個碉堡，每個碉堡可以向某個固定的方向每隔t秒放一次炮，炮彈不能穿越另一個碉堡，會被阻擋。人在移動的過程中不會被炮彈打到，比如說一個碉堡（0,0）的子彈速度3格每秒，同一時(shí)間人到了（0,3）這點(diǎn)，會被打死，而（0,2）則不會，問人能否到達(dá)（n，m）。

思路：本題關(guān)鍵就是先預(yù)處理每個時(shí)刻那些位置會有子彈，用remb[time][x][y]來記錄，并注意碉堡會擋住子彈，但不會被損壞。

#include<cstdio>#include<queue>#include<cstring>#include<cmath>using namespace std;const int maxt=1000+10;const int maxn2=100+5;struct castle{       //碉堡節(jié)點(diǎn) 	int t,v,x,y;     //時(shí)間間隔、速度、坐標(biāo) 	char c;	castle(int t=0,int v=0,int x=0,int y=0,char c='N'):t(t),v(v),x(x),y(y),c(c){}}cas[maxn2];struct node{	int x,y;	int time;   //走到當(dāng)前節(jié)點(diǎn)花了多少時(shí)間 	node(int x=0,int y=0,int time=0):x(x),y(y),time(time){}};bool vis[maxt][maxn2][maxn2];  bool remb[maxt][maxn2][maxn2]; //記錄每個時(shí)刻那些位置有炮彈 bool g[maxn2][maxn2];   //記錄碉堡的坐標(biāo) int m,n,k,d;int dir[][2]={{1,0},{-1,0},{0,-1},{0,1},{0,0}};bool isValid(node &nd){	return nd.x>=0&&nd.x<=m && nd.y>=0&&nd.y<=n;}void solve(){	memset(remb,false,sizeof(remb));		for(int i=0;i<k;i++){		int x=0,y=0;		switch(cas[i].c){			case 'N': x=-1;break;			case 'S': x=1;break;			case 'W': y=-1;break;			case 'E': y=1;		}		int x1,y1;        for(int j=1;;j++){        	x1=j*x+cas[i].x;           	y1=j*y+cas[i].y;        	if(x1<0 || x1>m || y1<0 || y1>n)break;        	if(g[x1][y1])break;                    	if(j%cas[i].v==0){  //子彈會停留的坐標(biāo)，時(shí)間=步數(shù)/速度         		for(int h=j/cas[i].v;h<=d;h+=cas[i].t){        			remb[h][x1][y1]=true;				}			}		}  }}bool judge(node &nd){   //當(dāng)逃到某點(diǎn)時(shí)，明顯無法到終點(diǎn)時(shí)，剪枝 	if(nd.time>d)return false;	int temp=abs(nd.x-m)+abs(nd.y-n);	return d-nd.time>=temp;}void bfs(){	memset(vis,false,sizeof(vis));	queue<node>q;	q.push(node(0,0,0));	vis[0][0][0]=true;	while(!q.empty()){		node u=q.front();		q.pop();		if(u.x==m && u.y==n){			PRintf("%d/n",u.time);			return ;		}		for(int i=0;i<5;i++){			node v=node(u.x+dir[i][0],u.y+dir[i][1],u.time+1);			if(isValid(v) && !vis[v.time][v.x][v.y] && !remb[v.time][v.x][v.y] && judge(v) && !g[v.x][v.y]){				q.push(v);				vis[v.time][v.x][v.y]=true;			}		}	}	printf("Bad luck!/n");}int main(){	while(scanf("%d%d%d%d",&m,&n,&k,&d)==4){		getchar();		memset(g,false,sizeof(g));		for(int i=0;i<k;i++){			scanf("%c",&cas[i].c);			scanf("%d%d%d%d",&cas[i].t,&cas[i].v,&cas[i].x,&cas[i].y);			getchar();    //吃掉換行 			g[cas[i].x][cas[i].y]=true;		}		solve();		bfs();	}	return 0;}