글 읽기 - 째로탈출2 22%에서 틀립니다.

pkgonan 7년 전 0

테스트 케이스 이외에 혹시 추가적인 예외 케이스 아시는분계씬가요?

22%에서 어떻게 틀리는지 모르겠네요 도와주세요

문제 접근은 4방향 재귀를 사용하였으며, 각 재귀 마다 동 서 남 북 빨간공과 파란공을 갈수 있는데까지

가도록 하였습니다.

만약 빨간공이 구멍에 들어가면 해당 카운트를 저장하고 있고

만약 파란공이 같은 방향으로 움직일때 구멍에 들어가면 4방향 재귀에서 다른방향으로 바뀌도록 continue 하였습니다.

도움 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N,M;
    static char[][] map;
    static int MIN = Integer.MAX_VALUE;
    static int[] xx = { 1, 0, -1, 0 };
    static int[] yy = { 0, 1 ,0, -1 };
    static int RED_START_i, RED_START_j, BLUE_START_i, BLUE_START_j, HOLE_i, HOLE_j;

    public static void main(String[] args) throws IOException{
        init();
        DFS(RED_START_i, RED_START_j, BLUE_START_i, BLUE_START_j, 1);
        if(MIN == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(MIN);
    }

    static void DFS(int RED_i, int RED_j, int BLUE_i, int BLUE_j, int cnt){
        if(cnt > 10) return;

        for(int i=0; i<4; i++){
            int BLUE_ni = BLUE_i;
            int BLUE_nj = BLUE_j;
            int RED_ni = RED_i;
            int RED_nj = RED_j;

            boolean isSuccess = true;
            int TMP_MIN = Integer.MAX_VALUE;

            while (isPromising(RED_ni + yy[i], RED_nj + xx[i])) {
                if (RED_ni + yy[i] == BLUE_ni && RED_nj + xx[i] == BLUE_nj) break;
                RED_ni += yy[i];
                RED_nj += xx[i];
                if(RED_ni == HOLE_i && RED_nj == HOLE_j) TMP_MIN = Math.min(TMP_MIN, cnt);
            }

            while (isPromising(BLUE_ni + yy[i], BLUE_nj + xx[i])) {
                if (BLUE_ni + yy[i] == RED_ni && BLUE_nj + xx[i] == RED_nj) break;
                BLUE_ni += yy[i];
                BLUE_nj += xx[i];
                if(BLUE_ni == HOLE_i && BLUE_nj == HOLE_j) isSuccess = false;
            }

            while (isPromising(RED_ni + yy[i], RED_nj + xx[i])) {
                if (RED_ni + yy[i] == BLUE_ni && RED_nj + xx[i] == BLUE_nj) break;
                RED_ni += yy[i];
                RED_nj += xx[i];
                if(RED_ni == HOLE_i && RED_nj == HOLE_j) TMP_MIN = Math.min(TMP_MIN, cnt);
            }

            while (isPromising(BLUE_ni + yy[i], BLUE_nj + xx[i])) {
                if (BLUE_ni + yy[i] == RED_ni && BLUE_nj + xx[i] == RED_nj) break;
                BLUE_ni += yy[i];
                BLUE_nj += xx[i];
                if(BLUE_ni == HOLE_i && BLUE_nj == HOLE_j) isSuccess = false;
            }

            if(!isSuccess) continue;
            else MIN = Math.min(MIN, TMP_MIN);

            DFS(RED_ni, RED_nj, BLUE_ni, BLUE_nj, cnt+1);
        }
    }

    static boolean isPromising(int i, int j){
        if(1>i || i>=N-1 || 1>j || j>=M-1) return false;
        if(map[i][j] == '#') return false;
        return true;
    }

    static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        M = Integer.parseInt(s[1]);
        map = new char[N][M];
        for(int i=0; i<N; i++){
            String ss = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = ss.charAt(j);
                if(map[i][j] == 'B'){
                    BLUE_START_i = i;
                    BLUE_START_j = j;
                }
                else if(map[i][j] == 'R'){
                    RED_START_i = i;
                    RED_START_j = j;
                }
                else if(map[i][j] =='O'){
                    HOLE_i = i;
                    HOLE_j = j;
                }
            }
        }
    }
}

smtsyh 7년 전 0

공이 구멍에 빠지는 상황에서도 공을 계속 끝까지 미는것 같은데.. 이 부분이 문제 아닐까요..?

toto 6년 전 1

작성자님 이 문제 해결하셨나요?

저도 같은 로직으로 문제 접근해서 풀고 있는데 22%에서 오류가 났는데 어디가 문제인지 모르겠네요..

pkgonan 6년 전 0

아뇨 해결 못했습니다.

공이 빠지면 해당 공의 위치를

0,0 같은데로 옮겨버려도 안되더라구요

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

문제

문제

출처

ICPC

째로탈출2 22%에서 틀립니다.

pkgonan 7년 전 0

smtsyh 7년 전 0

toto 6년 전 1

pkgonan 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말