[kuangbin带你飞]专题一 简单搜索 J - Fire!

题目：[kuangbin带你飞]专题一 简单搜索 J

思路

• 多起始点bfs
• 开始想的是两个队列进行搜索，让火先搜用火节点的步数是否等于nowJ的步数来处理每个时间段火烧的位置。用vis直接标记火烧的位置（后来发现这样会导致火不烧J走过的位置，改为设置地图该点为F）。
• wa了之后，没找到bug，考虑了另一种更简洁的方法，用一个队列搜索，用节点中的step=maxn表示火（火节点不用记录步数），只需要起始让火节点先进队就ok了。这样每个步骤都是火节点先出完，才到J节点
  (如循环到第i步骤时，所有步骤为i的火节点都在前面，经过四个方向处理后，标记了下一步火节点会出现的位置，同时将i+1步骤的火节点入队，此时出队的才是i步骤的J节点)。
• wa了之后改了很久，发现起始火节点不止一个。修改后就A了。
• 【注意】这种大量的输入数据的题目最好使用scanf，不然可能会tle，scanf输入字符地图的时候用scanf( "%s",mm[x][y])如果用%c的话还需要处理回车，太麻烦。

ac代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 0x3f3f3f3f 
using namespace std;
int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[1010][1010];
char mm [1010][1010];

int M,N;

struct node{
    int x;
    int y;
    int step;
};

bool check(node nextnode){
    if(nextnode.x<0||nextnode.y<0||nextnode.x>=N||nextnode.y>=M||mm[nextnode.x][nextnode.y]!='.')
        return false;
    return true;
}
queue<node> Q;
int bfs(){  
    while(!Q.empty()){
        node nownode;
        node nextnode;  
        nownode = Q.front();Q.pop();
///     cout <<"nownode" <<nownode.x<<" "<<nownode.y <<endl;
        if(nownode.step != MAXN)
            if(nownode.x == 0||nownode.y == 0||nownode.x == N-1||nownode.y == M-1){
                return nownode.step;
            }
        for(int i =0 ;i<4;i++){
            
            nextnode.x = nownode.x + mov[i][0];
            nextnode.y = nownode.y + mov[i][1];
            if(check(nextnode)){    
//          cout <<"nextnode" <<nextnode.x<<" "<<nextnode.y <<endl;
                if(nownode.step == MAXN){
                    mm[nextnode.x][nextnode.y] = 'F';
                    nextnode.step = MAXN;
                    Q.push(nextnode);
                }else if(!vis[nextnode.x][nextnode.y]){
                    vis[nextnode.x][nextnode.y] = true;
                    nextnode.step = nownode.step+1;
                    Q.push(nextnode);
                }
                
            } 
        }
    }
    return -1;
    
}

int main(){
    int T;
    cin>>T;
    
    while(T--){
        memset(vis,false,sizeof(vis));
        while(!Q.empty()) Q.pop();
        scanf("%d%d",&N,&M);
        node stJ;
        node stF;
        stF.step = MAXN;
        stJ.step = 0;
        for(int i = 0 ; i < N ; i++){
            scanf("%s",mm[i]);
            for(int j = 0 ; j < M ; j++ ){
                
                if(mm[i][j] == 'J'){
                    stJ.x = i;
                    stJ.y = j;
                }
                if(mm[i][j] == 'F'){
                    stF.x = i;
                    stF.y = j;
                    Q.push(stF);
                }
            }
        }
        Q.push(stJ);
        vis[stJ.x][stJ.y] = true;
        int ans;
        ans = bfs();
        if(ans < 0) printf("IMPOSSIBLE\n");
        else printf("%d\n", ans+1);
    } 
    
}