（BFS）UVA11624 Fire!

今天药忘吃喽~ 2022-04-12 05:53 182阅读 0赞

传送门：[UVA11624 Fire! ][UVA11624 Fire_]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3Mjc1Njgw_size_16_color_FFFFFF_t_70][]

注意：可能存在多个火源。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const int INF=0x3f3f3f3f;
    const int maxn=1010;
    char mp[maxn][maxn];
    int times[maxn][maxn],vis[maxn][maxn];
    int r,c;
     
    struct Node{
    	int x,y,step;
    }F,J;
     
    int dir[4][2]={
       {1,0},{-1,0},{0,1},{0,-1}};
    queue<Node> q;
     
    void bfs_f(){
    	Node p,nxt;
    	while(!q.empty()){
    		p=q.front();
    		q.pop();
    	    for(int i=0;i<4;i++){
    	    	nxt.x=p.x+dir[i][0];
    	    	nxt.y=p.y+dir[i][1];
    	    	nxt.step=p.step+1;
    	    	if(nxt.x>=0&&nxt.x<r&&nxt.y>=0&&nxt.y<c&&mp[nxt.x][nxt.y]!='#'&&times[nxt.x][nxt.y]==INF){
    	    		times[nxt.x][nxt.y]=nxt.step;
    	    		q.push(nxt);
    			}
    		}
    	}
    }
     
     
    int bfs_j(){
    	while(!q.empty())
    		q.pop();
    	memset(vis,0,sizeof(vis));
    	Node nxt,p;
    	J.step=0;
    	vis[J.x][J.y]=1;
    	q.push(J);
    	while(!q.empty()){
    		p=q.front();
    		q.pop();
    		for(int i=0;i<4;i++){
    	    	nxt.x=p.x+dir[i][0];
    	    	nxt.y=p.y+dir[i][1];
    	    	nxt.step=p.step+1;
    	    	if(nxt.x<0||nxt.x>=r||nxt.y<0||nxt.y>=c) return nxt.step;
    	    	if(mp[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y]&&nxt.step<times[nxt.x][nxt.y]){
    	    		vis[nxt.x][nxt.y]=1;
    	    		q.push(nxt);
    			}
    		}
    	}
    	return -1;
    }
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
        	int cnt=0;
        	scanf("%d%d",&r,&c);
        	memset(times,INF,sizeof(times));
        	while(!q.empty())   //多个输入样例，注意上次退出队列不一定为空。需要进行初始化
    			q.pop();
    			
        	for(int i=0;i<r;i++){
        		scanf("%s",mp[i]);
        		
        		for(int j=0;j<c;j++){
        			if(mp[i][j]=='J'){
        				J.x=i;
        				J.y=j;
    				}else if(mp[i][j]=='F'){
    					F.x=i;
    					F.y=j;
    					F.step=0;
    					q.push(F);
    					times[F.x][F.y]=F.step;
    				}
    			}
    		}
    		bfs_f();
    		int ans=bfs_j();
    		if(ans==-1) printf("IMPOSSIBLE\n");
    		else printf("%d\n",ans);
    	}
        return 0;
    }

[UVA11624 Fire_]: https://cn.vjudge.net/problem/UVA-11624
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3Mjc1Njgw_size_16_color_FFFFFF_t_70]: /images/20220412/b31af2418e0048488943d2629b1d9beb.png