글 읽기 - 예외테스트케이스를 못찾겠습니다.

qkrqudwn12 7년 전 0

처음에 불이 진행한 지점들을 숫자로 표기했습니다. fire라는 함수를 이용해서 불의 진행 cost를 기입해뒀고요

그후에 사람이 그숫자보다 작을때만 이동하게 했습니다. 이동후 밖에 탈출하면 값을 출력하고 탈출을 못한채로 큐가

빠지면 IMPOSSIBLE을 출력하게 했고요 과연 무엇이 잘못된것인지 모르겠습니다.ㅠㅠ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 불2 {
	static int N;
	static int M;
	static char array[][];
	static boolean check[][];
	static int fire[][];
	static int rl[] = { -1, 1, 0, 0 };
	static int ud[] = { 0, 0, -1, 1 };
	static int startx;
	static int starty;
	static Queue<Edge6> q = new LinkedList<Edge6>();

	public static boolean check(int x, int y) {
		return x >= 0 && x <= N + 1 && y >= 0 && y <= M + 1;
	}

	public static void bfs(int startx, int starty) {
		q.add(new Edge6(startx, starty, 0));
		check[startx][starty] = true;
		while (!q.isEmpty()) {

			Edge6 e = q.poll();
			int x = e.x;
			int y = e.y;
			int cost = e.cost;
			if (x == 0 || y == 0 || x == N + 1 || y == M + 1) {
				System.out.println(cost);
				return;
			}
			for (int i = 0; i < 4; i++) {
				int dx = x + rl[i];
				int dy = y + ud[i];
				if (check(dx, dy)) {
					if (array[dx][dy] == '#')
						continue;
					if (!check[dx][dy]) {
						if (array[dx][dy] == '.' && cost+1 < fire[dx][dy]) {
							q.add(new Edge6(dx, dy, cost + 1));
							check[dx][dy] = true;
						} else if (array[dx][dy] == 0) {
							q.add(new Edge6(dx, dy, cost + 1));
							check[dx][dy] = true;
						}

					}
				}
			}
		}
		System.out.println("IMPOSSIBLE");

	}

	public static void fire() {

		while (!q.isEmpty()) {
			int size = q.size();
			while (size-- > 0) {
				Edge6 e = q.poll();
				int x = e.x;
				int y = e.y;
				int cost = e.cost;
				for (int i = 0; i < 4; i++) {
					int dx = x + rl[i];
					int dy = y + ud[i];
					if (check(dx, dy)) {
						if ((array[dx][dy] == '.' || array[dx][dy] == '@') && fire[dx][dy] == -1) {
							fire[dx][dy] = cost + 1;
							q.add(new Edge6(dx, dy, cost + 1));
						}
					}
				}
			}
		}
	}

	public static void init() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				array[i][j] = 0;
				check[i][j] = false;
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int testcase = scan.nextInt();
		while (testcase-- > 0) {
			q = new LinkedList<Edge6>();
			M = scan.nextInt();
			N = scan.nextInt();
			array = new char[N + 2][M + 2];
			fire = new int[N + 2][M + 2];
			check = new boolean[N + 2][M + 2];
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					fire[i][j] = -1;
				}
			}
			for (int i = 1; i <= N; i++) {
				String str = scan.next();
				for (int j = 1; j <= M; j++) {
					array[i][j] = str.charAt(j - 1);
					if (array[i][j] == '@') {
						startx = i;
						starty = j;
					}
					if (array[i][j] == '*') {
						q.add(new Edge6(i, j, 0));
						fire[i][j] = 0;
					}
				}
			}
			fire();

			/*for (int i = 0; i <= N+1; i++) {
				for (int j = 0; j <= M+1; j++) {
					System.out.print(fire[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();*/
			bfs(startx, starty);
			/*for (int i = 0; i <= N+1; i++) {
				for (int j = 0; j <= M+1; j++) {
					System.out.print(array[i][j] + " ");
				}
				System.out.println();
			}*/
			init();
			q.clear();
		}
	}
}

class Edge6 {
	int x;
	int y;
	int cost;

	Edge6(int x, int y, int cost) {
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예외테스트케이스를 못찾겠습니다.

qkrqudwn12 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말