노틸러스
면접 대비시간 제한2초메모리 제한512 MB
R x C 격자와 ?가 섞인 M개의 이동 신호가 주어질 때, 섬에 들어가지 않는다는 조건을 지키며 현재 잠수함이 있을 수 있는 칸의 수를 센다. 신호를 역방향으로 적용해 가능한 시작 위치 집합을 좁히는 문제다.
문제
노틸러스는 비밀 잠수함으로, 바다를 항해하며 모습을 드러내지 않으려 한다.
바다는 R × C개의 칸으로 이루어진 격자로 나타내며, “#”은 섬, “.”은 바다를 뜻한다. 예를 들어:
...##....
..#.##..#
..#....##
.##...#..
....#....
노틸러스는 1분마다 잠수함이 향하려는 방향을 드러낼 수 있는 무선 신호를 보낸다. 방향은 항상 다음 중 하나이다: 북(N), 동(E), 남(S), 서(W). 위 오른쪽 그림과 같다.
Vytautas는 잠수함의 주기적인 신호를 가로채는 레이더를 만들었다. 지난 M분 동안 레이더는 M개의 무선 신호를 수집했고, 이는 M개의 문자로 이루어진 문자열로 나타난다. 예를 들어 “WS?EE??”와 같다. 일부 신호는 해독할 수 없었고, 이런 신호는 “?”로 표시된다.
Vytautas는 잠수함의 처음 위치를 모르지만, 바다 지도를 이용해 현재 위치를 알아내려 한다. 노틸러스가 항상 지도에서 바다 칸에만 머문다고 할 때, 현재 노틸러스가 있을 수 있는 서로 다른 칸의 개수를 구하도록 Vytautas를 도와라.
입력
첫째 줄에 세 정수 R, C, M이 주어진다.
다음 R개의 줄은 바다 지도를 나타내는 “#”과 “.” 문자로 이루어진 R × C 격자이다.
입력의 마지막 줄은 Vytautas가 가로챈 신호를 나타내며, {N, E, S, W, ?}에 속하는 M개의 문자로 이루어진 문자열이다.
출력
노틸러스가 현재 있을 수 있는 서로 다른 위치의 개수를 하나의 정수로 출력한다.