79brue   8달 전

민식이와 영식이는 $N \times M$ 크기의 직사각형 보드 위에서 게임을 한다. 민식이와 영식이는 보드 위에 로봇 한 대씩을 가지고 있다. 보드의 각 칸에는 장애물이 있거나 없으며, 각 로봇은 장애물이 없는 서로 다른 칸에 놓여 있다. 또한 장애물이 없는 칸 중 하나는 도착 칸이다.

민식이의 로봇이 영식이의 로봇보다 먼저 도착 칸에 도착할 경우, 또는 민식이의 로봇만 도착 칸에 도착할 경우 민식이가 이긴다. 그 외의 모든 경우 (민식이의 로봇이 도착 칸에 도착하지 못하거나, 두 로봇이 같은 시점에 도착 칸에 도달하거나, 영식이의 로봇이 먼저 도착 칸에 도착할 경우) 영식이가 이긴다. 이동 과정에서 민식이의 로봇과 영식이의 로봇은 같은 칸에 위치할 수 있다.

로봇은 명령을 통해 움직이며, 각 명령은 알파벳 한 글자로 나타낼 수 있다.

  • S: 남쪽으로 한 칸 이동한다.
  • N: 북쪽으로 한 칸 이동한다.
  • E: 동쪽으로 한 칸 이동한다.
  • W: 서쪽으로 한 칸 이동한다.

두 로봇은 같은 명령을 들으며, 그 명령의 목록은 각 명령에 대응되는 문자를 순서대로 나열한 문자열 $C$로 나타낼 수 있다. 로봇이 각 명령을 들을 때마다, 로봇은 해당 명령을 수행하거나 무시할 수 있다. 만약 명령이 로봇을 보드를 벗어나게 만들거나, 장애물이 있는 곳으로 가게 만든다면, 로봇은 명령을 자동으로 무시한다. 두 로봇은 이후 받을 명령의 목록을 알고 있고, 항상 각 로봇이 도착 칸에 되도록 빨리 가도록 최적의 선택을 한다.

당신은 보드의 모양과 명령이 주어졌을 때, 민식이의 로봇이 이길 수 있는 가장 빠른 시작 시간을 출력해야 한다. 여기서 시작 시간이 $T$라는 것은, 두 로봇이 전체 명령 목록 $C$를 듣는 대신, $C$의 $T$번 문자부터 듣기 시작한다는 것이다. 여기서 $T$는 $0$-index로 생각한다. 만약 그러한 $T$가 없다면 대신 -1을 출력한다.

---

첫째 줄에 $N$과 $M$이 주어진다. ($1 \le N, M \le 50$)

둘째 줄부터 $N$개의 줄에 보드의 모양이 주어진다. ‘.’은 빈 공간, ‘#’는 장애물, ‘Y’는 민식이의 시작 위치, ‘F’는 영식이의 시작 위치, ‘X’는 도착 위치이다. 'Y', 'F', 'X'는 각각 한 개씩만 주어진다.

마지막 줄에는 명령 목록 $C$가 주어진다. $C$의 길이는 최대 $2500$이고, $S$는 문자 'S', 'E', 'N', 'W'로만 이루어져 있다.

---

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

seungjae123   8달 전

원본은 진짜 난해하네요. 읽기 쉽게 수정해주셔서 감사합니다.

추가로 개선됐으면 하는 부분 덧붙여볼게요.

- 북쪽에서 -> 북쪽으로 오타 수정.

- 두 로봇이 같은 칸에 있을 수 있다고 명시해주는 문장 추가.

- 남쪽 이동 명령이 S를 사용하고 있기 때문에 문자열 S 대신 다른 알파벳을 사용하면 좋을 것 같습니다.

79brue   8달 전

피드백 감사합니다. 반영하였습니다.

댓글을 작성하려면 로그인해야 합니다.