글 읽기 - 반례를 모르겠습니다.

kp6069 3년 전 0

bfs로 구현했고 각각의 공들을 이동시켜준다음 두 가지 공이 동시에 밖으로 빠질 경우에만 continue 시켜주어 제외시키는 방식으로 구현했습니다.

예제 테스트 케이스 모두 맞는거 확인했고, 게시판 내 다른 반례들도 모두 확인했는데 여전히 '틀렸습니다' 에러가 뜨네요...

반례 찾아주시면 감사하겠습니다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static class Point {
		int bi;
		int bj;
		int ri;
		int rj;
		int cnt;

		Point(int bi, int bj, int ri, int rj, int cnt) {
			this.bi = bi;
			this.bj = bj;
			this.ri = ri;
			this.rj = rj;
			this.cnt = cnt;
		}
	}

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

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]);
			int M = Integer.parseInt(input[1]);

			char[][] A = new char[N][M];
			int bi = -1;
			int bj = -1;
			int ri = -1;
			int rj = -1;

			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < M; j++) {
					A[i][j] = str.charAt(j);
					if (A[i][j] == 'o') {
						if (bi == -1) {
							bi = i;
							bj = j;
						} else if (ri == -1) {
							ri = i;
							rj = j;
						}
					}
				}
			}

			// bfs 알고리즘
			Queue<Point> q = new LinkedList<Point>();
			int[][][][] c = new int[N][M][N][M];
			q.offer(new Point(bi, bj, ri, rj, 0));
			c[bi][bj][ri][rj] = 1;

			while (!q.isEmpty()) {
				Point p = q.poll();
				if ((p.bi == -1 && p.bj == -1) || (p.ri == -1 && p.rj == -1)) {
					System.out.println(p.cnt);
					System.exit(0);
				}

				if (p.cnt > 10)
					break;

				for (int i = 0; i < dx.length; i++) {
					int newbi = p.bi;
					int newbj = p.bj;
					int newri = p.ri;
					int newrj = p.rj;

					// 파란공
					if (p.bi + dx[i] < 0 || p.bi + dx[i] >= N || p.bj + dy[i] < 0 || p.bj + dy[i] >= M) {
						newbi = -1;
						newbj = -1;
					} else if (A[p.bi + dx[i]][p.bj + dy[i]] != '#') {
						newbi += dx[i];
						newbj += dy[i];
					}

					// 빨간공
					if (p.ri + dx[i] < 0 || p.ri + dx[i] >= N || p.rj + dy[i] < 0 || p.rj + dy[i] >= M) {
						newri = -1;
						newrj = -1;
					} else if (A[p.ri + dx[i]][p.rj + dy[i]] != '#') {
						newri += dx[i];
						newrj += dy[i];
					}

					if (newbi == -1 && newbj == -1 && newri == -1 && newrj == -1)
						continue;

					if ((newbi == -1 && newbj == -1) || (newri == -1 && newrj == -1)) {
						q.offer(new Point(newbi, newbj, newri, newrj, p.cnt + 1));
						continue;
					}
					if (c[newbi][newbj][newri][newrj] == 0) {
						q.offer(new Point(newbi, newbj, newri, newrj, p.cnt + 1));
						c[newbi][newbj][newri][newrj] = 1;
					}
				}
			}
			System.out.println(-1);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

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

문제

문제

출처

ICPC

반례를 모르겠습니다.

kp6069 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말