시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 11 10 52.632%

문제

요즘 한창 잘 나가고 있는 XH 주식회사에서는 어린이용 장난감을 주력 사업으로 밀고 있다. 그 중 인기가 많은 제품은 역시 미로 탈출 게임인 째로탈출이다. 째로탈출은 다음 그림처럼, 미로 형태의 보드를 이용한 게임이다. 

째로탈출의 보드는 세로 N, 가로 M의 크기로 이뤄진 격자 형식으로 되어있다. 가장 바깥의 행과 열은 모두 막혀 있다. 그림에는 없지만 째로탈출에는 빨간 구슬과 파란 구슬이 하나씩 들어있고, 구멍이 하나 있다. 게임의 목적은 빨간 구슬을 구멍을 통해 빼내는 것이다. 이 때, 파란 구슬이 구멍에 들어가면 안된다.

물론 째로탈출 보드에는 투명한 아크릴판이 덮여있어서 직접 빼내는 것은 불가능하고, 중력을 이용해 이리저리 굴리면서 빼내게 된다. 플레이어가 할 수 있는 동작은 다음과 같이 네 종류가 있다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기.

각각의 동작에서 공은 동시에 움직이게 되며, 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 격자의 한 칸을 모두 차지한다. 

기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로/가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로만으로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이내에 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

예제 입력

5 5
#####
#..B#
#.#.#
#RO.#
#####

예제 출력

1

예제 입력 2

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 2

5

예제 입력 3

7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######

예제 출력 3

5

예제 입력 4

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########

예제 출력 4

-1

예제 입력 5

3 7
#######
#R.O.B#
#######

예제 출력 5

1

예제 입력 6

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########

예제 출력 6

7

예제 입력 7

3 10
##########
#.O....RB#
##########

예제 출력 7

-1

힌트

출처