[BOJ]5427号火(Java)
4356 ワード
質問する
5427号:火
に答える
典型的なBFSシミュレーション問題!
すべての論理の順序と火が広がる過程をよく記入すればいい.
BFS論理順序
1.Depth増加時に拡散しない
2.行く途中に火があれば続けてもいい
3.終了条件の確認
4.ルート移動可能パスのナビゲート
火が広がる過程
1.新しい火の広がりを保存するリストを宣言
2.現在のディレクトリを迂回して新しいディレクトリに追加
3.現在のディレクトリの初期化:いずれにしても広がりました->タイムアウトに注意してください.
4.既存のリストに新しい拡散リストを追加
コード(JAVA)
import java.io.*;
import java.util.*;
public class Main{
static int[] di = {-1,0,1,0}; // 상 좌 하 우
static int[] dj = {0,-1,0,1};
static int N, M, res;
static char[][] map;
static List<int[]> fire;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc = 0 ; tc < T ; tc++){
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new char[N][M];
fire = new ArrayList<>();
int[] cur = new int[2];
for(int i =0 ; i < N ; i++){
String str = br.readLine();
for(int j =0 ; j < M ; j++){
map[i][j] = str.charAt(j);
if(map[i][j] == '*'){
fire.add(new int[]{i, j});
}
else if(map[i][j] == '@'){
cur[0] = i; cur[1] = j;
map[i][j] = '.';
}
}
}
res = -1;
findWay(cur[0], cur[1]);
System.out.println((res==-1)?"IMPOSSIBLE":res);
}
}
private static void findWay(int i, int j) {
Queue<int[]> q = new ArrayDeque<>();
int time = 0;
boolean[][] visited = new boolean[N][M];
q.offer(new int[]{i, j, 0});
visited[i][j] = true;
while(!q.isEmpty()){
int[] cur = q.poll();
/*
1. depth 늘어날 때마다 불 확산: 해주지 않으면 같은 초에서도 계속 불이 확산되는 상황 발생
*/
if(time != cur[2]){
spreadFire();
time = cur[2];
}
/*
2. 가려는 길에 불이 확산되어 있으면 다음 경로 탐색
*/
if(map[cur[0]][cur[1]] == '*') continue;
/*
3. 종료 조건 체크
*/
if(cur[0] == 0 || cur[0] == N-1 || cur[1] == 0 || cur[1] == M-1){
res = cur[2]+1; // 건물 밖으로 나가는 시간까지 +1
return;
}
/*
상근이 이동 가능 경로 탐색
*/
for(int d = 0; d < 4 ; d ++){
int ni = cur[0] + di[d];
int nj = cur[1] + dj[d];
if(0<=ni&&ni<N && 0<=nj&&nj<M){
if(!visited[ni][nj] && map[ni][nj] == '.'){
visited[ni][nj] = true;
q.offer(new int[]{ni, nj, cur[2]+1});
}
}
}
}
}
private static void spreadFire() {
List<int[]> tmp = new ArrayList<>();
for(int[] f: fire){
for(int d = 0 ; d < 4 ; d++){
int ni = f[0] + di[d];
int nj = f[1] + dj[d];
if(0<=ni&&ni<N && 0<=nj&&nj<M){
if(map[ni][nj] == '.'){
map[ni][nj] = '*';
tmp.add(new int[]{ni, nj});
}
}
}
}
fire.clear();
fire.addAll(tmp);
}
}
Reference
この問題について([BOJ]5427号火(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-5427번-불-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol