Problems
창고지기라는 이름으로도 알려져 있는 소코반 게임은 유명한 고전 게임 중의 하나이다.
벽들로 막혀있는 지도상에서 사람을 움직여서 짐을 원하는 위치까지 밀어 운반하는 게임이다.
원래 게임에서는 여러 개의 짐을 여러 개의 목적지까지 하나씩 모두 옮기게 되어 있지만,
여기서는 간단하게 1개의 짐을 정해진 목적지까지 옮기는 것으로 하겠다.
지도는 위 그림처럼 격자로 되어있다. 검정색 상자를 x표시의 위치까지 옮기는 것이 게임의 목적이다.
이 때 빨간 선대로 상자가 움직이는 것이 최단 경로이다.
상자를 이렇게 움직이기 위해서 사람을 파란 선대로 이동시켜서 상자를 밀어야 한다.
물론 상자를 밀 때 앞쪽에 벽이 있으면 그 쪽으로 상자를 밀수가 없으며, 상자를 이동시킬 반대 방향의 칸에 사람이 위치에 있어야 한다.
게임 지도의 상황이 입력으로 주어질 때, 목적지까지 이동시키기 위해서 상자를 밀어야 하는 최소 횟수를 출력하는 프로그램을 작성하시오.
Input
첫 번째 줄에는 지도의 가로 크기 m과 세로 크기 n이 주어진다.(4≤m, n≤20)
둘째 줄부터 n개의 줄에는 길이 m의 문자열들이 주어진다.
각 문자열들은 지도의 내용을 나타내며, W는 벽, O는 빈 곳, M은 사람, B는 상자, X는 목적지를 의미한다.
Output
상자를 목적지까지 이동시키기 위해서 상자를 밀어야 하는 최소 횟수를 출력한다.
만약 목적지까지 상자를 이동시킬 수 없으면 -1을 출력한다.
Example
7 8
WWWWWWW
WMOOOOW
WOWWOOW
WOBOOWW
WWWWOWO
WWOOOWW
OWOOOXW
OWWWWWW
6
You must sign in to write code.