https://www.acmicpc.net/problem/5427
5427번: 불
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에
www.acmicpc.net
분류 : BFS, 최단 경로
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
public static PrintWriter out;
static int[] dx = { 0, -1, 0, 1 };
static int[] dy = { -1, 0, 1, 0 };
static char[][] maze;
static int[][] MoveTime, JohnTime;
static int R, C;
static int JHour, FHour;
static boolean check = false;
static final int inf = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int T = sc.nextInt();
while(T-->0){
C = sc.nextInt();
R = sc.nextInt();
maze = new char[R][C];
MoveTime = new int[R][C];
JohnTime = new int[R][C];
boolean FireCheck = false;
Queue<JPoint> John = new LinkedList<JPoint>();
Queue<FPoint> Fire = new LinkedList<FPoint>();
for (int r = 0; r < R; r++) {
String str = sc.next();
maze[r] = str.toCharArray();
}
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
MoveTime[i][j] = inf;
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (maze[i][j] == '@') {
John.add(new JPoint(i, j));
JohnTime[i][j] = 0;
} else if (maze[i][j] == '*') {
Fire.add(new FPoint(i, j));
FireCheck = true;
MoveTime[i][j] = 0;
}
}
}
FBFS(Fire);
JBFS(John);
if (check) {
System.out.println(JHour);
} else {
System.out.println("IMPOSSIBLE");
}
JHour =0;
FHour = 0;
check = false;
}
out.close();
}
private static void JBFS(Queue<JPoint> john) {
JHour = 1;
boolean[][] visited = new boolean[R][C];
loop1: while (!john.isEmpty()) {
int Jsize = john.size();
for (int sz = 0; sz < Jsize; sz++) {
JPoint Jp = john.poll();
int Jx = Jp.x;
int Jy = Jp.y;
visited[Jx][Jy] = true;
for (int ar = 0; ar < 4; ar++) {
int cx = Jx + dx[ar];
int cy = Jy + dy[ar];
if (cx >= 0 && cx < R && cy >= 0 && cy < C) {
if (maze[cx][cy] != '#' && maze[cx][cy] != '*' && !visited[cx][cy]) {
if (MoveTime[cx][cy] > JohnTime[Jx][Jy] + 1) {
JohnTime[cx][cy] = JHour;
visited[cx][cy] = true;
john.add(new JPoint(cx, cy));
}
}
} else {
check = true;
break loop1;
}
}
}
JHour++;
}
}
private static void FBFS(Queue<FPoint> fire) {
FHour = 0;
boolean[][] visited = new boolean[R][C];
while (!fire.isEmpty()) {
int Fsize = fire.size();
for (int sz = 0; sz < Fsize; sz++) {
FPoint Fp = fire.poll();
int Fx = Fp.x;
int Fy = Fp.y;
visited[Fx][Fy] = true;
for (int ar = 0; ar < 4; ar++) {
int cx = Fx + dx[ar];
int cy = Fy + dy[ar];
if (cx >= 0 && cx < R && cy >= 0 && cy < C)
if (maze[cx][cy] != '#' && !visited[cx][cy]) {
MoveTime[cx][cy] = FHour + 1;
visited[cx][cy] = true;
fire.add(new FPoint(cx, cy));
}
}
}
FHour++;
}
}
}
class JPoint {
int x;
int y;
JPoint(int x, int y) {
this.x = x;
this.y = y;
}
}
class FPoint {
int x;
int y;
FPoint(int x, int y) {
this.x = x;
this.y = y;
}
}
이 문제를 풀다 보니 Fire!! 문제에서 내가 제출했던 코드의 문제점을 알아내었다.
그래서 그 부분을 해결해서 제출하니 무난히 통과~
'PS' 카테고리의 다른 글
[BOJ]3055번: 탈출 (0) | 2017.04.02 |
---|---|
[BOJ]1194번 : 달이 차오른다, 가자. (0) | 2017.03.31 |
[BOJ]4179번 : Fire! (0) | 2017.03.31 |
[BOJ]7569번 : 토마토 (0) | 2017.03.29 |
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |