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

柔光的暖阳◎ 2024-02-17 19:11 5阅读 0赞

题意：有一个人要从(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;
    }