HDU 3533 Escape (bfs + 预处理 + 剪枝)

 题意：有一个人要从(0，0)走到（n，m），图中有k个碉堡，每个碉堡可以向某个固定的方向每隔t秒放一次炮，炮弹不能穿越另一个碉堡，会被阻挡。人在移动的过程中不会被炮弹打到，比如说一个碉堡（0,0）的子弹速度3格每秒，同一时间人到了（0,3）这点，会被打死，而（0,2）则不会，问人能否到达（n，m）。

思路：本题关键就是先预处理每个时刻那些位置会有子弹，用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{       //碉堡节点 	int t,v,x,y;     //时间间隔、速度、坐标 	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;   //走到当前节点花了多少时间 	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]; //记录每个时刻那些位置有炮弹 bool g[maxn2][maxn2];   //记录碉堡的坐标 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){  //子弹会停留的坐标，时间=步数/速度         		for(int h=j/cas[i].v;h<=d;h+=cas[i].t){        			remb[h][x1][y1]=true;				}			}		}  }}bool judge(node &nd){   //当逃到某点时，明显无法到终点时，剪枝 	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;}