3687 - 게임 - 주차장
Time Limit: 5s
Memory Limit: 128MB
- Description
-
합법적인 이유로 컴퓨터 프로그래밍 시간에 게임을 해보자! 대신 허용하는 게임을 제한하였다. 후후...
"러쉬아워" 라는 이름의 게임을 들어본 적이 있는 사람이 있을 것이다. 굳이 러쉬아워란 이름이 아니더라도, 왕년에 야후꾸러기에서 플래쉬게임이 흥했을 때 이것저것 미니게임을 해봤다면 한번쯤 해봤을 게임이다. 일단 아래의 그림을 보자.
게임은 6x6 판에서 이루어진다. 판에는 1x2 , 1x3 또는 2x1, 3x1 짜리 크기의 블럭들이 배치되있다. 이 블럭들은, 가로로 긴 블럭은 가로로만 움직일 수 있고, 세로로 긴 블럭은 세로로만 이동시킬 수 있다. 각 블럭은 이동경로 상에 벽이나 다른 블럭에 의해 막히지 않을 때 까지 이동할 수 있다. 이런 상황에서 1x2 짜리 크기를 가진 특정 블럭(그림에서는 C에 해당)을 오른쪽 끝으로 탈출시키는 것이 이 게잉의 목적이다.
이 게임에서 "턴" 의 개념은, 블럭을 한번 움직일 때마다 한 턴이 소모된다고 보면 된다. 만약 2x1짜리 블럭을 위로 한칸 올렸다면, 이것은 한턴이 소모된것이다. 그리고 2x1 블럭을 한번에 위로 4칸을 올리는 행위 역시 한 턴을 소모한 것이다.)
프로 게이 머인 Gravek**per는 이 게임을 수백만번 플레이해서 필승법을 거의 완벽하게 익혀냈다. 만약 임의의 맵이 주어지게 된다면 퍼즐을 푸는데 최소 몇 턴이 필요한지를 경험적으로 알아낼 수 있다고한다. 하지만 애석하게도 그는 이를 알고리즘화시키진 못했다.
우리는 이 게임의 규칙을 방금 들었다. 맵이 주어졌을 때 퍼즐을 푸는 최소 턴 수를 알아내는 프로그램을 작성하여 프로 게이 머를 놀래켜보자.
- Input
입력은 여러개의 테스트데이터로 구성되어져있다.
각 데이터마다 첫째 줄에는 탈출시키고싶은 "특별한 블럭"의 이름이 대문자 알파벳으로 주어진다.
그 다음 6개의 줄에는 6x6 짜리 맵 정보가 주어진다. 맵을 표현하는데 사용되는 문자는 대문자 알파벳과 '.' 이다.
'.'은 빈 공간을 의미하며 각 알파벳은 블럭의 이름을 뜻한다. 블럭은 1x2, 1x3, 2x1, 3x1 네가지 타입 중 하나이며, 같은 이름을 가진 블럭은 그 크기만큼 연속해서 배치된다고 한다. 이름이 같은 서로 다른 블럭은 없다. "특별한 블럭"은 항성 1x2 짜리 블럭이며, 맵의 어딘가에는 반드시 존재한다.
데이터의 첫째줄에 '*' 이 들어오면 데스트데이터가 종료된다.
- Output
각 테스트데이터마다 블럭을 탈출시키는데 필요한 최소 턴 수를 출력한다. 만약 특별한 블럭이 탈출이 불가능하다면 -1을 출력한다.
- Sample Input
-
C ..AB.. ..AB.. CCAB.. ...... .DDEE. ...... A ...... ...... ...... ...... AA.... ...... Z .ZZ..X .....X .....X .....Y .....Y .....Y *
- Sample Output
-
5 1 -1
- Source
Regionals 2009, North America - Southeast USA