원본은 진짜 난해하네요. 읽기 쉽게 수정해주셔서 감사합니다.
추가로 개선됐으면 하는 부분 덧붙여볼게요.
- 북쪽에서 -> 북쪽으로 오타 수정.
- 두 로봇이 같은 칸에 있을 수 있다고 명시해주는 문장 추가.
- 남쪽 이동 명령이 S를 사용하고 있기 때문에 문자열 S 대신 다른 알파벳을 사용하면 좋을 것 같습니다.
1137번 - 로봇 레이스
원본은 진짜 난해하네요. 읽기 쉽게 수정해주셔서 감사합니다.
추가로 개선됐으면 하는 부분 덧붙여볼게요.
- 북쪽에서 -> 북쪽으로 오타 수정.
- 두 로봇이 같은 칸에 있을 수 있다고 명시해주는 문장 추가.
- 남쪽 이동 명령이 S를 사용하고 있기 때문에 문자열 S 대신 다른 알파벳을 사용하면 좋을 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
79brue 8달 전 5
민식이와 영식이는 $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'로만 이루어져 있다.---
첫째 줄에 문제의 정답을 출력한다.