말린(Marlin)은 아들을 잃어버려서 아들을 찾고 있는 물고기다. 다행히도 그는 바다를 헤엄치던 거북이 신시아(Cynthia)를 만났고, 신시아는 오빠들인 월리(Wally)와 시모어(Seymour)와 함께 있었다. 신시아는 말린이 정확히 어디로 가야 하는지 알고 있고, 매우 정확하게 길을 안내해 줄 수 있다. 말린은 똑똑해서 지시를 완벽하게 따를 수 있지만, 긴 지시 목록을 계속 기억하고 따라가는 것은 문제가 될 수 있다. 신시아는 지시 목록을 짧게 만드는 방법을 찾아야 한다.

말린은 R행 C열의 행렬에서 산다. 행렬의 일부 칸은 위험해서 들어갈 수 없다. 말린과 아들은 현재 서로 다른(위험하지 않은) 칸에 있으며, 말린의 아들은 다른 칸으로 이동하지 않는다. 신시아는 말린에게 다음과 같은 프로그램 형태로 길 안내를 주기로 했다. 프로그램은 한 줄에 하나씩 쓰인 명령들의 목록이며, 각 명령은 다음 5가지 중 하나이다:

N: 북쪽(위)으로 한 칸 이동,
S: 남쪽(아래)으로 한 칸 이동,
W: 서쪽(왼쪽)으로 한 칸 이동,
E: 동쪽(오른쪽)으로 한 칸 이동, 그리고
G(i): 명령 목록의 i번째 줄로 점프(1부터 센다).

처음 4가지 명령 중 하나를 실행한 뒤에는, 다음 줄이 있다면 말린은 목록의 다음 줄로 이동한다. 다음 줄이 없다면, 말린은 이후로 영원히 그 자리에 가만히 선다.

예를 들어 말린이 다음 프로그램을 따른다고 하자.

1: N
2: E
3: G(6)
4: S
5: G(1)
6: W
7: G(4)

그러면 말린은 북쪽으로 이동(1번 줄), 동쪽으로 이동(2번), 물리적으로 움직이지 않고 6번 줄로 점프(3번), 서쪽으로 이동(6번), 4번 줄로 점프(7번), 남쪽으로 이동(4번), 1번 줄로 점프(5번), 북쪽으로 이동(1번)... 이런 식으로 진행한다.

어느 시점이든 말린과 아들이 같은 칸에 있게 되면, 둘은 재회하고 말린은 더 이상 어떤 명령도 따르지 않는다. 거북이 신시아는 말린이 위험한 칸에 들어가거나 행렬의 경계를 벗어나는 일이 한 번도 없으면서 아들과 같은 칸으로 가도록 만드는 프로그램의 줄 수(명령 수)의 최솟값을 알고 싶다. 모든 G 명령은 프로그램에 실제로 존재하는 줄로만 점프해야 한다.

#10354 upload 1 done - how_to_reg -

Go To Considered Helpful timer 30s memory 1024MB

#10354

Go To Considered Helpful 30s 1024MB