로봇 청소기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

명령이 주어질 때마다 로봇이 상자에 막힐 때까지 미끄러지듯 이동한다. 시작 칸을 포함해 로봇이 지나간 서로 다른 칸의 수를 구한다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, 구현, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

로봇 청소기가 격자 모양의 창고를 청소한다. 창고의 일부 칸에는 무거운 상자가 놓여 있다. 청소기는 일련의 명령에 따라 움직인다. 명령은 위("^"), 오른쪽(">"), 아래("v"), 왼쪽("<")이다. 로봇이 명령을 받으면 그 방향으로 상자가 가로막을 때까지 최대한 멀리 간다. 로봇 청소기가 한 번이라도 위치한 칸은 모두 청소된다. 시작 칸도 포함된다. 창고의 모양, 로봇의 시작 위치, 명령의 순서가 주어졌을 때, 명령이 모두 끝난 뒤 청소된 서로 다른 칸의 수를 구하라.

입력

첫째 줄에 세 정수 $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"를 포함하는 칸은 정확히 하나임이 보장된다. 또한 격자의 가장자리에 있는 모든 칸은 "#"임이 보장된다.

출력

로봇이 청소한 서로 다른 칸의 수를 정수로 출력한다.

예제4

예제 1

입력

5 5 4
v>^v
#####
#O#.#
#...#
##..#
#####

예상 출력

예제 2

입력

6 7 7
>>^<v><
#######
#.#.#.#
#.....#
#.....#
##O..##
#######

예상 출력

예제 3

입력

3 12 3
<<<
############
#.#.....O.##
############

예상 출력

예제 4

입력

8 10 14
<v>^<v>v<^^><>
##########
#.#......#
#....#...#
##......O#
#........#
#..#.....#
#....#...#
##########

예상 출력