시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 9 4 4 80.000%

문제

민식이는 영식이와 직사각형 보드에 두 로봇이 있는 게임을 한다. 각 보드의 칸은 비어있거나 장애물 또는 로봇의 시작점이거나 도착점이다. 만약 로봇이 도착 칸에 도착한다면, 민식이는 이 게임을 이기게 된다. 두 로봇은 서로 동시에 도착한다면, 도착 칸에 도착하지 못한다면, 민식이는 게임을 영식이에게 지게 된다.

두 로봇은 다음과 같은 명령이 있다.

  • S: 남쪽으로 한 칸
  • N: 북쪽에서 한 칸
  • E: 동쪽으로 한 칸
  • W: 서쪽으로 한 칸

시간이 지날 때, 두 로봇은 같은 명령을 듣는다. 로봇은 명령을 수행하거나, 무시할 수 있다. 만약 명령이 로봇을 보드를 벗어나게 만들거나, 장애물이 있는 곳으로 가게 만든다면, 로봇은 명령을 자동으로 무시한다. 두 로봇은 항상 각 로봇이 도착 칸에 되도록 빨리 가도록 최적의 선택을 한다.

보드의 모양과 명령이 주어졌을 때, 민식이의 로봇이 이기는 것이 보장되는 가장 빠른 시작 시간을 출력한다. 시작 시간이 T라는 것은 명령의 T번째 문자부터 명령을 수행한다는 뜻이다. 만약 그러한 것이 없다면 -1을 출력한다.
 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 모양이 주어진다. ‘.’은 빈 공간, ‘#’는 장애물, ‘Y’는 민식이의 시작 위치, ‘F’는 영식이의 시작 위치, ‘X’는 도착 위치이다. 마지막 줄에는 명령이 주어진다. 명령의 길이는 최대 2500이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

8 8
########
#......#
#.Y....#
#.F.#..#
#...X..#
#...#..#
#......#
########
SSEEESSW

예제 출력

2

힌트

출처