ICPC 2011 Mid-Central Regional Programming Contest G번- 소코반 > 문제은행 : 정보올림피아드&알고리즘




3546 : 소코반

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
15 회   
시도횟수
33 회   

문제

​소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수는 항상 같다. 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙대로 움직일 수 있다.​

 

  1. 캐릭터에게 지시한 방향에 빈 칸(박스나 벽이 아닌 곳)이 있는 경우에는 그 칸으로 이동한다.
  2. 지시한 방향에 박스가 있는 경우에는, 박스를 한 칸 밀고 그 칸으로 이동한다. 박스가 이동할 칸이 비어있지 않다면 캐릭터와 박스 모두 이동하지 않는다.
  3. 지시한 방향에 벽이 있는 경우, 또는 박스가 있는데 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.
  4. 모든 박스를 목표점으로 이동시키면 게임이 끝난다. 이 때, 게임이 끝난 후의 입력은 모두 무시된다.

 

 상수는 소코반 게임을 하기 위해 간단한 소코반 프로그램을 작성해 보려고 한다. 플레이어의 입력이 순서대로 주어졌을 때, 게임이 어떻게 진행되는지를 구하는 프로그램을 작성하시오.​ 


입력형식

첫째 줄에는 행과 열의 수 R, C가 주어진다. (4 ≤ R ≤ 15, 4 ≤ C ≤ 15) 다음 R개 줄에는 현재 게임의 상태가 주어진다. 모든 줄은 C개의 문자로 이루어져 있다. 마지막 줄에는 플레이어의 입력이 순서대로 주어지며 길이는 최대 50이다. 위, 아래, 왼쪽, 오른쪽은 U, D, L, R로 나타낸다.

 

게임의 상태는 아래와 같은 문자로 나타내어진다.

 

문자

. 빈 공간

#

+ 비어있는 목표점

b 박스

B 목표점 위에 있는 박스

w 캐릭터

W 목표점 위에 있는 캐릭터

 

참고로, 첫 번째 입력은 문제의 그림과 같다.

 

입력으로 주어지는 모든 데이터는 항상 캐릭터가 한 명이고, 박스의 수와 목표점의 수는 같다. 또, 목표점 위에 올라가 있지 않은 박스는 적어도 한 개 있으며, 가장 바깥쪽 칸은 항상 벽이다.

 


출력형식

​만약 게임이 끝났으면 complete를, 아니면 incomplete를 출력한다. 그 다음 줄부터 R개 줄에 모든 입력이 끝난 후 게임의 상태를 출력한다.

 


입력 예

8 9
#########
#...#...#
#..bb.b.#
#...#w#.#
#...#b#.#
#...++++#
#...#..##
#########
ULRURDDDUULLDDD

출력 예

incomplete
#########
#...#...#
#..bb...#
#...#.#.#
#...#.#.#
#...+W+B#
#...#b.##
#########

입력 예

6 7
#######
#..####
#.+.+.#
#.bb#w#
##....#
#######
DLLUDLULUURDRDDLUDRR

출력 예

complete
#######
#..####
#.B.B.#
#.w.#.#
##....#
#######


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP