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

badcandy 7년 전 0

bfs로 사람의 영역을 넓힌다음 불을 옮기는 식으로 구현하였는데

예외 테스트 케이스 부분을 못찾겠습니다..

어떤부분에서 틀린걸까요..?

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

public class Fire {

	private static int maxY, maxX;

	private static boolean flag;
	
	private static char[][] map = new char[1000][1000];

	private static boolean[][] visited = new boolean[1000][1000];

	private static final int[] dy = { -1, 0, 1, 0 };

	private static final int[] dx = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int i = 0; i < T; i++) {

			maxX = sc.nextInt();
			maxY = sc.nextInt();

			for (int j = 0; j < maxY; j++) {

				String input = sc.next();
				for (int k = 0; k < maxX; k++) {

					map[j][k] = input.charAt(k);
				}
			}
			
			int ret = solve();
			System.out.println(ret == -1 ? "IMPOSSIBLE" : ret);
		}
		

	}
	
	private static int solve() {
		
		int count = 0;
		
		while (true) {
			
			flag = false;
			
			++count;
			
			for (int i = 0; i < maxY; i++) {
				
				for (int j = 0; j < maxX; j++) {
					
					if (!visited[i][j] && map[i][j] == '@')
						if (find(i, j))	return count;
				}
			}
			
			if (!flag)	return -1;
			
			for (int i = 0; i < maxY; i++) {
				Arrays.fill(visited[i], 0, maxX, false);
			}
			
			
			
			for (int i = 0; i < maxY; i++) {
				
				for (int j = 0; j < maxX; j++) {
					
					if (!visited[i][j] && map[i][j] == '*')
						moveFire(i, j);
				}
			}
			
			for (int i = 0; i < maxY; i++) {
				Arrays.fill(visited[i], 0, maxX, false);
			}
		}
	}

	private static void moveFire(int startY, int startX) {

		Queue<Point> q = new LinkedList<>();

		q.add(new Point(startY, startX));

		while (!q.isEmpty()) {

			int hereY = q.peek().y;
			int hereX = q.remove().x;

			if (hereY >= 0 && hereX >= 0 && hereY < maxY && hereX < maxX && !visited[hereY][hereX]) {

				visited[hereY][hereX] = true;

				if (map[hereY][hereX] == '*')
					for (int i = 0; i < 4; i++) {

						int nextY = hereY + dy[i];
						int nextX = hereX + dx[i];

						q.add(new Point(nextY, nextX));
					}

				else if (map[hereY][hereX] == '.' || map[hereY][hereX] == '@')
					map[hereY][hereX] = '*';
			}
		}
	}

	private static boolean find(int startY, int startX) {

		Queue<Point> q = new LinkedList<>();

		q.add(new Point(startY, startX));

		while (!q.isEmpty()) {

			int hereY = q.peek().y;
			int hereX = q.remove().x;

			if (hereY == maxY || hereX == maxX || hereY == -1 || hereX == -1)	return true;

			if (hereY >= 0 && hereX >= 0 && hereY < maxY && hereX < maxX && !visited[hereY][hereX]) {

				visited[hereY][hereX] = true;

				if (map[hereY][hereX] == '@')
					for (int i = 0; i < 4; i++) {

						int nextY = hereY + dy[i];
						int nextX = hereX + dx[i];

						q.add(new Point(nextY, nextX));
					}

				else if (map[hereY][hereX] == '.') {
					
					map[hereY][hereX] = '@';
					flag = true;
				}
					
			}
		}

		return false;
	}

	private static class Point {

		public int y, x;

		public Point(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}


	}
	
	private static void print() {

		System.out.println("-----------------------------------------------");
		for (int i = 0; i < maxY; i++) {

			for (int j = 0; j < maxX; j++) {

				System.out.printf("%6c", map[i][j]);


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

}

badcandy 7년 전 0

불이 옮겨지고 난 뒤에 사람이 움직이면

7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######

이 테스트 케이스 같은 경우 탈출 못하지 않나요??

이 예제에 대한 답은 5라고 생각하는데 흠..

초기 케이스
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
불을 옮김
###.###
#*#.#*#
#*...*#
#.....#
#..@..#
#######
사람을 옮김
###.###
#*#.#*#
#*...*#
#..@..#
#.@@@.#
#######
불을 옮김
###.###
#*#.#*#
#**.**#
#*.@.*#
#.@@@.#
#######
사람을 옮김
###.###
#*#.#*#
#**@**#
#*@@@*#
#@@@@@#
#######
불을 옮김
###.###
#*#.#*#
#*****#
#**@**#
#*@@@*#
#######
이렇게 됨으로써 탈출하지 못하는거 아닌가요??
제가 문제를 잘못이해하고 있는지 ㅠㅠ

tols91 7년 전 0

마지막에 불이 위치를 덮칠때 좌표에서는 사람이 지워지지만 큐에 남아있어 다음위치로 이동 할수있어요

badcandy 7년 전 0

아 그렇게 구현해야할까요?

조언 감사합니다 ㅎㅎ 일단 그렇게 구현해보겠습니다

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

문제

문제

출처

ICPC

5427번 예외 테스트케이스를 못찾겠습니다 ㅠㅠ

badcandy 7년 전 0

tols91 7년 전 0

badcandy 7년 전 0

tols91 7년 전 0

badcandy 7년 전 0

tols91 7년 전 0

badcandy 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말