题目:[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);
}
}
网友评论