BOJ 12698 Portal (Large)

문제 링크:

문제 내용

사각 격자로 이루어진 미로에서 포탈건을 사용하여 시작점에서 끝점으로 가는 최단 거리를 구하세요.

포탈건은 노란색과 파란색 중 하나를 선택한 뒤 현재 위치에서 상하좌우 중 한 방향으로 쏠 수 있으며, 그 방향의 가장 가까운 벽면에 그 색깔의 포탈이 만들어집니다.

노란색과 파란색의 포탈이 모두 열려 있는 상태에서, 한쪽 포탈이 열린 벽 안으로 이동하면 반대쪽 포탈이 열린 벽 밖으로 나오게 됩니다.

만약 이미 열려 있는 색깔의 포탈건을 쏘면, 기존의 그 색깔의 포탈은 닫히고 새로운 위치에 그 색깔의 포탈이 열립니다.

두 색깔의 포탈을 같은 벽면 위에 열 수 없습니다.

상하좌우로 한 칸 이동하는 데는 1의 시간이 걸리며, 포탈건을 쏴서 포탈이 만들어지기까지는 시간이 걸리지 않습니다.

입력

첫 줄에는 테스트 케이스의 개수 $N$이 주어집니다. ($1 \le N \le 50$)

각 테스트 케이스에서, 첫 줄에는 행 개수 $R$과 열 개수 $C$가 주어지고, 그다음 $R$줄에는 미로가 주어집니다. ($1 \le R, C \le 15$)

미로에서 O는 시작점, X는 도착점, .는 빈 공간, #는 벽을 나타냅니다. 미로의 바깥쪽은 벽으로 둘러싸여 있으며, 그러한 벽에도 포탈을 만들 수 있습니다.

출력

각 테스트 케이스에 대해, Case #<테스트 번호>:를 출력하고, 문제의 정답을 출력합니다. 어떻게 해도 도착점에 다다를 수 없다면 THE CAKE IS A LIE를 대신 출력합니다.

문제 풀이