문제
N*M 크기의 보드판이 있다. 이 보드판의 가장자리는 모두 막혀 있고, 보드에는 구멍이 하나 있다.
보드에서 1×1크기의 칸을 가득 채우는 사이즈의 흰 구슬과 검정 구슬이 각각 하나씩 들어있다.
이 때, 흰 구슬만 꺼내면 승리하는 게임을 진행하려고 한다.
보드판이 투명한 유리 덮개로 덮어져있기 때문에 구슬을 손으로 이동 시킬 수는 없다.
보드판을 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울여 중력으로 구슬을 굴리는 동작만 가능하다 .
각각의 동작에서 두 개의 공은 동시에 움직인다. 구슬을 기울이는 동작은 두 구슬이 모두 벽에 부딪쳐 더이상 이동하지 않을 때까지 유지된다.
검정 구슬이 구멍에 빠지면 실패이다. (흰 구슬과 검정 구슬이 동시에 구멍에 빠져도 실패이다.)
최초의 보드 상태가 주어졌을 때, 최소 몇 번 만에 흰 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다.
다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.
이 문자열은 '.', '#', 'O', 'W', 'B' 로 이루어져 있다.
'.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다.
'W'은 흰 구슬의 위치, 'B'는 검정 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 흰 구슬과 검정 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 흰 구슬을 구멍을 통해 빼낼 수 있는지 출력한다.
만약, 10번 이하로 움직여서 흰 구슬만 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
예제 #1
5 9
#########
#O....#.#
#.W.#...#
#......B#
#########
2
예제 #2
8 4
####
##.#
#.W#
#.B#
#.O#
#..#
#.##
####
3
로그인해야 코드를 작성할 수 있어요.