글 읽기 - 1194번 83%에서 틀렸다네요

kukuku0517 5년 전 0

애매하게 83%에서 오류가나서 어디가 문제인지 모르겠네요..

비트마스크적용도하였고 도착지점이 여러개인것도 고려했습니다

답변감사합니다!!

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int row = scan.nextInt();
        int col = scan.nextInt();
        char[][] map = new char[row][col];
        boolean[][][] visitedWithKeys = new boolean[51][51][1 << 7];


        State state = null;
        for (int i = 0; i < row; i++) {
            String s = scan.next();
            for (int j = 0; j < col; j++) {
                char c = s.charAt(j);
                map[i][j] = c;
                if (c == '0') {
                    state = new State(i, j, 0, 0);
                    visitedWithKeys[i][j][getKey(0, 0)] = true;
                    map[i][j] = '.';
                }
            }
        }

        Queue<State> q = new LinkedList<>();
        q.offer(state);
        boolean hasEscaped = false;
        int count = -1;
        while (!q.isEmpty() && !hasEscaped) {
            State temp = q.poll();
//            System.out.printf("[%d,%d] keys:%d \n", temp.x, temp.y, temp.keys);

            for (int i = 0; i < 4; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
                if (visitedWithKeys[nx][ny][temp.keys]) continue;
                visitedWithKeys[nx][ny][temp.keys] = true;
                if (map[nx][ny] == '#') continue;


//                    System.out.printf("[%d,%d]>[%d,%d]\n", temp.x, temp.y, nx, ny);

                char now = map[nx][ny];

                if (now == '1') {
                    hasEscaped = true;
                    count = temp.count + 1;
                    break;
                } else if ('a' <= now && now <= 'z') {
                    int key = now - 'a';
                    int keys = getKey(temp.keys, key);
                    State newState = new State(nx, ny, keys, temp.count + 1);
                    visitedWithKeys[nx][ny][keys] = true;
                    q.offer(newState);
                } else if ('A' <= now && now <= 'Z') {
                    int door = now - 'A';
                    if (hasKey(temp.keys, door)) {
//                            System.out.printf("has key : %c\n", now);
                        State newState = new State(nx, ny, temp.keys, temp.count + 1);
                        q.offer(newState);
                    }
                } else {
                    q.offer(new State(nx, ny, temp.keys, temp.count + 1));
                }

            }
        }

        System.out.println(count);


    }

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

    static class State {
        int x, y;
        int keys;
        int count;

        public State(int x, int y, int keys, int count) {
            this.x = x;
            this.y = y;
            this.keys = keys;
            this.count = count;
        }

    }


    static int getKey(int keys, int newKey) {
        return keys | 1 << newKey;
    }

    static boolean hasKey(int keys, int key) {
        if ((keys & 1 << key) == 0) return false;
        return true;
    }


}

hllee1021 3년 전 0

혹시 이거 해결하셨나요ㅠ 똑같은데서 막히는데 도저히 모르겠네요.

choko100 1년 전 0

안녕하세요, 위의 코드는 key 를 만났을 때만 visited 배열에 표시하고 있는 것 같습니다.

큐에 넣는 q.offer()가 호출되기 전에는 항상 visited 배열에 표시 해야할 것 같습니다.

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

문제

문제

출처

ICPC

1194번 83%에서 틀렸다네요

kukuku0517 5년 전 0

hllee1021 3년 전 0

choko100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말