수집 로봇

시간 제한2초메모리 제한512 MB

요약
기둥이 있는 격자에서 주어진 명령 문자열에 따라 로봇을 회전시키고 이동시키며 방문한 서로 다른 스티커의 개수를 센다.
난이도

쉬움10점 중 3점

유형
시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

로보랜드에서 인기 있는 스포츠 중 하나가 로봇 랠리다. 랠리는 정사각형 칸이 NN행 MM열로 놓인 거대한 직사각형 경기장에서 열린다. 어떤 칸은 비어 있고, 어떤 칸에는 로보랜드의 인공지능이 아주 좋아하는 월드컵 스티커가 놓여 있으며, 어떤 칸은 경기장 천장을 받치는 기둥이 차지한다. 로봇은 기둥이 있는 칸을 빼고 경기장의 어느 칸이든 지날 수 있고, 기둥은 로봇의 이동을 막는다.

랠리에서 로봇이 지나는 경로는 명령 문자열로 정해진다. 명령은 문자 D, E, F 중 하나이며 각각 오른쪽으로 90도 회전, 왼쪽으로 90도 회전, 앞으로 한 칸 이동을 뜻한다.

로봇은 경기장의 정해진 시작 위치에서 출발해 주어진 명령을 순서대로 그대로 수행한다. 로봇이 스티커가 놓인 칸을 밟으면 그 스티커를 수집한다. 스티커는 다시 놓이지 않으므로 각 스티커는 한 번만 수집된다. 로봇이 기둥이 있는 칸으로 이동하려 하면 미끄러져서 원래 칸에 그대로 남고 방향도 그대로다. 경기장 밖으로 나가려 할 때도 마찬가지다.

기둥과 스티커의 위치를 담은 경기장 지도와 로봇의 명령 문자열이 주어질 때, 로봇이 수집한 스티커의 개수를 구하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 NN, MM, SS가 공백으로 구분되어 주어진다 (1≤N,M≤1001 \le N, M \le 100, 1≤S≤5×1041 \le S \le 5 \times 10^4). 각각 경기장의 행 수, 경기장의 열 수, 로봇에게 주어진 명령의 개수다.

이어지는 NN개의 줄은 경기장의 한 행씩을 나타내며, 각 줄은 MM개의 문자로 된 문자열이다. 먼저 나오는 행이 가장 북쪽 행이고, 한 행에서 먼저 나오는 열이 가장 서쪽 열이다.

경기장의 각 칸은 다음 문자 중 하나다.

  • . 빈 칸
  • * 월드컵 스티커가 놓인 칸
  • # 기둥이 있는 칸
  • N, S, L, O 로봇이 출발하는 칸이고 경기장에 하나만 있다. 문자는 로봇의 처음 방향을 나타내며 N은 북쪽, S는 남쪽, L은 동쪽, O는 서쪽이다.

테스트 케이스의 마지막 줄에는 D, E, F 중의 문자 SS개로 이루어진 명령 문자열이 주어진다.

마지막 테스트 케이스 다음 줄에는 공백 하나로 구분된 0 세 개만 주어진다.

출력

입력에 주어진 각 랠리마다 한 줄에 정수 하나를 출력한다. 그 랠리에서 로봇이 수집한 스티커의 개수다.

예제2

  1. 예제 1

    입력
    3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0
    예상 출력
    0
1
3

  2. 예제 2

    입력
    2 1 1
*
N
F
2 1 1
S
*
F
1 2 1
L*
F
1 2 1
*O
F
0 0 0
    예상 출력
    1
1
1
1