토끼가 정보섬에 올라온 이유
시간 제한1초메모리 제한256 MB
토끼가 오른쪽, 오른쪽 위, 오른쪽 아래로만 움직이며 벽과 당근, 옆문이 있는 격자를 지날 때, 옆문으로 나가기 전까지 모을 수 있는 당근의 최댓값을 구한다.
문제
토끼가 정보섬에 올라왔다!
정보섬은 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