로봇 청소기

로봇 청소기가 격자 모양의 창고를 청소하며, 일부 칸에는 무거운 상자가 놓여 있다. 청소기는 위쪽("^"), 오른쪽(">"), 아래쪽("v"), 왼쪽("<") 명령으로 이루어진 명령열에 따라 움직인다. 로봇은 명령을 받으면 상자에 가로막힐 때까지 해당 방향으로 갈 수 있는 만큼 이동한다. 시작한 칸을 포함하여 로봇 청소기가 한 번이라도 있었던 모든 칸은 청소된다. 창고의 모습, 로봇의 시작 위치, 명령열이 주어질 때, 명령열의 실행이 끝난 후 청소된 서로 다른 칸의 수를 구한다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| 이 그룹은 포스터(https://www.progolymp.se/2021/affisch.pdf)에 있는 단 하나의 테스트 케이스로 구성된다.

$2$ |$20$| $R=3$

$3$ |$30$| $N \times R \times C \le 1000$

$4$ |$30$| 추가 제한이 없다.

• 첫 번째 줄에는 세 정수 $R$ ($3 \le R \le 2000$), $C$ ($3 \le C \le 2000$), $N$ ($1 \le N \le 2000$)이 주어진다. $R$과 $C$는 격자 모양 창고의 행과 열의 수이고, $N$은 명령열의 길이이다.

• 두 번째 줄에는 "^", ">","v","<"로 이루어진 길이 $N$의 문자열, 즉 로봇에 전달되는 명령열이 주어진다.

• 다음 $R$개의 줄에는 격자 모양 창고의 모습이 주어진다. 이 중 $i$번째 줄에는 창고의 $i$번째 행을 나타내는 $C$개의 문자가 주어진다. 각 문자는 칸이 비어 있으면 점 ".", 칸에 상자가 있으면 사각형 "#", 로봇의 시작 위치이면 "O"이다. 정확히 한 칸에 "O"가 있음이 보장된다. 또한 격자 가장자리의 모든 칸이 "#"임이 보장된다.

로봇이 청소하는 서로 다른 칸의 수를 나타내는 정수 하나를 출력한다.