6134 : 어두운 방 탈출
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 격자 방이 주어집니다. 0은 시작점, 1은 탈출구, '#'은 벽, '.'은 빈칸입니다.
알파벳 소문자 'a'~'f'는 열쇠이고, 대문자 'A'~'F'는 해당 열쇠를 소지해야만 열 수 있는 문입니다.
지수가 시작 위치에서 출발하여 문들을 열쇠로 열면서 탈출구로 향할 때의 최단 시간을 구하십시오.
알파벳 소문자 'a'~'f'는 열쇠이고, 대문자 'A'~'F'는 해당 열쇠를 소지해야만 열 수 있는 문입니다.
지수가 시작 위치에서 출발하여 문들을 열쇠로 열면서 탈출구로 향할 때의 최단 시간을 구하십시오.
입력 설명
첫째 줄에 행 크기 N과 열 크기 M (1 ≤ N, M ≤ 50)이 주어집니다.
둘째 줄부터 N개의 줄에 격자 정보가 줄바꿈 없이 한 행씩 입력됩니다.
둘째 줄부터 N개의 줄에 격자 정보가 줄바꿈 없이 한 행씩 입력됩니다.
출력 설명
탈출구 1에 도달하는 최단 시간(초)을 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0.a
##A
1..
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6도움
열쇠 획득 상태를 6비트 정수(0~63)인 비트마스크(Bitmask)로 관리하고, BFS 방문 상태 공간을
visited[r][c][key_mask]로 선언하여 최단 거리를 탐색하십시오.