Portal

$Portal^{TM}$은 Valve Software에서 개발하고 배급한 일인칭 퍼즐/플랫폼 게임이다. 이 게임의 발상은 벽에 두 개의 포털을 만든 다음, 한 포털로 뛰어들어 다른 포털로 나오는 것이었다. 이 문제에도 비슷한 발상이 사용되지만, Portal을 플레이해 보았다고 가정하지 않는다.

이 문제에서 당신은 R행 C열 격자 안에 있다. 또한 격자의 다른 어딘가에는 맛있는 케이크가 있다. 당신은 매우 배가 고프며, 가능한 한 적은 이동으로 케이크에 도착하고 싶다. 북쪽, 남쪽, 동쪽 또는 서쪽의 빈 칸으로 이동할 수 있다. 또한 벽에 포털을 만드는 능력이 있다.

케이크에 도달하는 데 도움을 주기 위해, 노란색 포털과 파란색 포털이라는 두 종류의 포털을 발사할 수 있는 포털 건을 가지고 있다. 포털 건을 북쪽, 남쪽, 동쪽 또는 서쪽으로 발사하면 포털이 생성된다. 그러면 에너지 구체가 방출되어 처음 부딪히는 벽에 포털을 만든다. 이 문제에서는 포털 건을 발사하는 것이 이동 횟수에 포함되지 않는다는 점에 유의하라. 포털 건을 케이크를 향해 발사하면 에너지 구체는 케이크를 그대로 통과한다.

노란색 포털과 파란색 포털을 만든 뒤에는 노란색 포털을 통과해 파란색 포털에 도착하거나, 그 반대로 이동할 수 있다. 이 포털들을 사용하면 케이크에 훨씬 더 빨리 도달할 수도 있다! 노란색 포털과 파란색 포털을 모두 만든 뒤에만 포털을 사용할 수 있다.

다음 격자를 살펴보자:

회색 칸은 벽을, 흰색 칸은 빈 칸을 나타내며, 빨간색 원은 당신의 위치를 나타낸다.

파란색 포털을 동쪽으로 발사한다고 하자. 포털은 처음 부딪히는 벽에 생성되며, 결과는 다음과 같다:

이제 노란색 포털을 남쪽으로 발사한다고 하자:

그다음 남쪽으로 한 번 이동한다:

이제 흥미로운 부분이다. 남쪽으로 한 번 더 이동하면 노란색 포털을 통과해 파란색 포털로 간다:

어느 때든 노란색 포털은 하나, 파란색 포털도 하나만 존재할 수 있다. 예를 들어 파란색 포털을 서쪽으로 만들려고 하면 기존의 파란색 포털은 사라진다:

포털은 같은 색의 다른 포털이 발사될 때만 사라진다.

포털은 벽의 한쪽 면에 생성된다는 점에 유의하라. 벽의 동쪽 면에 포털이 있다면, 그 포털을 통과하려면 동쪽에서 벽 안으로 이동해야 한다. 그렇지 않으면 벽 안으로 이동하게 되는데, 이는 있을 법하지 않다.

마지막으로, 두 포털을 서로 겹쳐 놓을 수 없다. 이미 포털이 있는 벽의 면을 향해 포털을 발사하려 하면 두 번째 포털은 생성되지 않는다.

미로, 당신의 초기 위치, 케이크의 위치가 주어질 때, 케이크에 도달할 수 있다면 필요한 최소 이동 횟수를 구해야 한다. 포털 건을 발사하는 것은 이동 횟수에 포함되지 않는다는 점을 기억하라.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

N = 200 1 ≤ R, C ≤ 8

큰 데이터 세트 (테스트 세트 2 - 비공개)

N = 50 1 ≤ R, C ≤ 15

입력의 첫 번째 줄에는 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 정수 R과 C가 주어진다. 이어지는 R개의 줄에는 각각 지도를 나타내는 C개의 문자가 주어진다:

• .은 빈 칸을 나타낸다;

• #은 벽을 나타낸다;

• O은 당신의 시작 위치를 나타낸다; 그리고

• X은 케이크의 위치를 나타낸다.

각 케이스에는 정확히 하나의 O 문자와 하나의 X 문자가 있다.

격자 바깥의 칸은 모두 벽이며, 이 벽들을 사용해 포털을 만들 수 있다.

각 테스트 케이스마다 "Case #X: Y"을 한 줄에 출력한다(따옴표는 명확성을 위한 것이다). 여기서 X는 테스트 케이스의 번호이고, Y는 케이크에 도달하는 데 필요한 최소 이동 횟수이다. 케이크에 도달할 수 없다면 "THE CAKE IS A LIE"을 출력한다(따옴표는 명확성을 위한 것이다).

첫 번째 케이스의 이동 순서는 다음과 같다(포털 건을 발사하는 것은 이동 횟수에 포함되지 않는다는 점에 유의하라):

• 동쪽으로 한 칸 이동한다.

• 파란색 포털을 북쪽으로 발사한다.

• 노란색 포털을 남쪽으로 발사한다.

• 파란색 포털을 통과해 북쪽으로 한 칸 이동한다.

• 파란색 포털을 동쪽으로 발사한다.

• 노란색 포털을 통과해 남쪽으로 한 칸 이동한다.

• 서쪽으로 한 칸 이동한다.

• 맛있고 촉촉한 케이크를 먹는다.

$Portal^{TM}$은 Valve Inc의 상표이다. Valve Inc.은 Google Code Jam을 보증하지 않으며 아무런 관련도 없다.