문제
진호는 중력 뒤집기 게임을 만들고 있다. 중력 뒤집기 게임은 NxM 크기의 격자 모양의 화면에서 진행되며, 조금의 조작을 통해 플레이어를 도착지점까지 움직여야 한다. 추가 규칙은 아래와 같다.
만약 플레이어가 도착지점이 있는 곳에 있으면 중력 방향 격자가 어떻든지 간에 게임 클리어가 된다.
만약 플레이어의 중력 방향(아래쪽 혹은 위쪽) 격자가 비어있다면 플레이어는 중력 방향으로 떨어진다. 플레이어가 떨어지는 동안에는 버튼이 먹히지 않으며 플레이어가 화면 밖으로 나가게 되면 게임 오버가 된다. (화면 밖의 격자는 모두 빈 공간이다)
플레이어가 1, 2번 상황이 아니라면 버튼을 눌러 플레이어를 조작할 수 있다.
L/R 버튼을 누르면 플레이어는 한 칸 왼쪽/오른쪽으로 움직인다. 만약 플레이어가 가려는 곳이 벽으로 막혀 있으면 플레이어는 움직이지 않는다.
G 버튼을 누르면 중력이 반대 방향으로 바뀐다. 단, 처음에는 중력이 아래쪽으로 작용한다.
진호는 게임을 깨지 못 하는 사람들을 위해 힌트를 제공하려고 한다. 맵이 주어질 때 중력을 뒤집는 최소 횟수를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 맵의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 500) 두 번째 줄부터 N개의 줄에는 맵의 모양이 주어진다. ‘.’는 빈 공간, ‘#’는 벽, ‘C’는 시작점, ‘D’는 도착점을 의미한다.
출력
맵을 클리어하기 위해 눌러야 하는 G 버튼의 최소 횟수(중력을 뒤집는 최소 횟수)를 출력한다. 만약 맵을 클리어할 수 없다면 -1을 출력한다.
예제
5 5
#####
#...#
#...D
#C...
##.##
3
플레이어는 G, R, R, G, R, G를 차례대로 눌러서 맵을 클리어할 수 있다.
로그인해야 코드를 작성할 수 있어요.