시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 619 162 129 27.922%

문제

토끼가 정보섬에 올라왔다!

정보섬은 N행 M열의 격자로 나타낼 수 있으며, 어째서인지 여기저기에 당근이 떨어져 있다. 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. 토끼의 왼쪽에선 사나운 늑대가 쫓아오고 있어서, 토끼는 →, ↘, ↗ 방향으로만 이동한다. 토끼는 나가는 길에 최대한 많은 당근을 줍고싶다. 정문은 늑대 때문에 위험하므로 쪽문으로 나가야 하며, 토끼가 당근을 줍기 위해서는 그 당근이 있는 위치를 지나야 한다. 토끼가 어떤 쪽문에 도착했을때 반드시 그 문으로 탈출할 필요는 없으며, 더 움직여서 다른 쪽문으로 탈출해도 된다. 토끼는 얼마나 많은 당근을 주워갈 수 있을까?

토끼의 이동을 명확하게 정의하면 다음과 같다. 격자의 r행 c열 위치를 (r, c)라고 하자. 토끼의 현재위치가 (r, c)일때, 한 번의 이동으로 도착할 수 있는 위치는 (r+1, c+1), (r, c+1), (r-1, c+1)의 3가지다. 벽이나 격자의 밖으로는 이동할 수 없다.

입력

첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반드시 하나만 주어지며, 'O'는 없거나 여러 개일 수 있다.

출력

토끼가 정보섬을 빠져나가면서 얻을 수 있는 당근의 최대 개수를 출력한다. 정보섬에서 빠져나갈 수 없는 경우에는 -1을 출력한다.

제한

1 ≤ N,M ≤ 1000

예제 입력 1

3 5
RC#OO
.#CCC
..O..

예제 출력 1

3

(1,1) → (1,2) → (2,3) → (2,4) → (1,5)
이외의 경우는 탈출할 수 없거나 당근의 개수가 최대가 아니다.

예제 입력 2

2 4
CC#O
RC##

예제 출력 2

-1