boj)4179 - 불!
2020. 10. 17. 16:59ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_4179 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Queue<Node> qF = new LinkedList<>();
static Queue<Node> qJ = new LinkedList<>();
static char[][] a;
static int row, col, nx, ny, ans;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
input();
if (bfs()) System.out.println(ans);
else System.out.println("IMPOSSIBLE");
}
public static void input() throws IOException {
st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
col = Integer.parseInt(st.nextToken());
a = new char[row][col];
for (int i = 0; i < row; i++) {
a[i] = br.readLine().toCharArray();
for (int j = 0; j < col; j++) {
if (a[i][j] == 'F') {
qF.offer(new Node(i, j, 0));
} else if (a[i][j] == 'J') {
qJ.offer(new Node(i, j, 0));
}
}
}
}
public static boolean bfs() {
while (!qJ.isEmpty()) {
int size = qF.size();
for (int i = 0; i < size; i++) {
Node now = qF.poll();
for (int j = 0; j < 4; j++) {
nx = now.x + dx[j];
ny = now.y + dy[j];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (a[nx][ny] == '#' || a[nx][ny] == 'F') continue;
a[nx][ny] = 'F';
qF.offer(new Node(nx, ny, now.d + 1));
}
}
size = qJ.size();
for (int i = 0; i < size; i++) {
Node now = qJ.poll();
for (int j = 0; j < 4; j++) {
nx = now.x + dx[j];
ny = now.y + dy[j];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) {
ans = now.d + 1;
return true;
}
if (a[nx][ny] == '#' || a[nx][ny] == 'F' || a[nx][ny] == 'J') continue;
a[nx][ny] = 'J';
qJ.offer(new Node(nx, ny, now.d + 1));
}
}
}
return false;
}
static private class Node {
int x;
int y;
int d;
public Node(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
}
- 실패
- 불 먼저 이동후 - > 지훈이는 불을 피해다니며 이동
- 지훈이가 완전히 탈출할때까지 반복
- 지훈이가 만약 범위를 벗어난다면 그때의 시간인 now.d + 1을 출력후 return true
- 큐가 빌때까지 반복했는데도 탈출하지 못한다면 return false
- true : ans+1, false : impossible 출력
'PS > boj' 카테고리의 다른 글
boj)7569 - 토마토 (0) | 2020.10.19 |
---|---|
boj)1697 - 숨바꼭질 (0) | 2020.10.17 |
boj)1926 - 그림 (0) | 2020.10.15 |
boj)10866 - 덱 (0) | 2020.10.14 |
boj)4889 - 안정적인 문자열 (0) | 2020.10.14 |