로봇 대회

세게드 대학교의 AI 연구자들이 로봇 프로그래밍 대회를 연다. 친구 Hanga도 이 대회에 참가하기로 했다. 목표는 헝가리의 유명한 목양견 품종인 풀리의 지능을 본떠 최고의 Pulibot을 프로그래밍하는 것이다.

Pulibot은 $(H+2) \times (W+2)$ 격자로 이루어진 미로에서 테스트된다. 행은 북쪽에서 남쪽으로 $-1$부터 $H$까지, 열은 서쪽에서 동쪽으로 $-1$부터 $W$까지 번호가 붙는다. 셀 $(r,c)$는 $r$행 $c$열의 셀이다. 여기서 $-1 \le r \le H$, $-1 \le c \le W$이다.

$0 \le r < H$이고 $0 \le c < W$인 셀 $(r,c)$에 인접한 셀은 4개이다. 서쪽 셀은 $(r,c-1)$, 남쪽 셀은 $(r+1,c)$, 동쪽 셀은 $(r,c+1)$, 북쪽 셀은 $(r-1,c)$이다.

셀 $(r,c)$는 $r=-1$, $r=H$, $c=-1$, $c=W$ 중 하나가 성립하면 경계 셀이다. 그 밖의 셀은 장애물 셀이거나 빈 셀이다. 빈 셀은 0부터 $Z_{MAX}$까지의 정수로 표현되는 색을 가진다. 처음에는 모든 빈 셀의 색이 0이다.

예를 들어, $H=4$, $W=5$이고 셀 $(1,3)$에 장애물이 하나 있는 미로를 보자. 장애물은 십자가로 표시하고, 경계 셀은 음영으로 표시한다. 빈 셀에 적힌 숫자는 각 셀의 색이다.

셀 $(r_0,c_0)$에서 셀 $(r_\ell,c_\ell)$까지 길이가 $\ell$($\ell > 0$)인 경로는 서로 다른 빈 셀들의 나열 $(r_0,c_0), (r_1,c_1), \ldots, (r_\ell,c_\ell)$이며, 연속된 두 셀은 인접해야 한다. 길이가 $\ell$인 경로는 정확히 $\ell+1$개의 셀을 포함한다.

대회에서는 셀 $(0,0)$에서 셀 $(H-1,W-1)$까지 가는 경로가 적어도 하나 존재하는 미로를 사용한다. 따라서 셀 $(0,0)$과 $(H-1,W-1)$은 반드시 빈 셀이다.

하가는 미로에서 어느 셀이 빈 셀이고 어느 셀이 장애물인지 알지 못한다. 그녀의 과제는 알려지지 않은 미로에서 Pulibot이 셀 $(0,0)$에서 $(H-1,W-1)$까지의 최단 경로(길이가 가장 짧은 경로)를 찾도록 프로그램을 작성하는 것이다. Pulibot의 사양과 대회 규칙은 아래와 같다.

Pulibot의 사양

$-1 \le r \le H$, $-1 \le c \le W$ 범위의 셀 $(r,c)$의 상태는 다음과 같이 정한 정수이다.

• 셀 $(r,c)$가 경계 셀이면 상태는 $-2$이다.
• 셀 $(r,c)$가 장애물 셀이면 상태는 $-1$이다.
• 셀 $(r,c)$가 빈 셀이면 상태는 그 셀의 색이다.

Pulibot의 프로그램은 단계들의 순서로 실행된다. 각 단계에서 Pulibot은 주변 셀들의 상태를 인식하고, 인식한 상태에 따라 정해진 명령을 수행한다.

현재 단계를 시작할 때 Pulibot이 빈 셀 $(r,c)$에 있다고 하자. 이때 단계는 다음과 같이 진행된다.

1. Pulibot은 현재 상태 배열 $S = [S[0], S[1], S[2], S[3], S[4]]$를 인식한다. $S[0]$은 셀 $(r,c)$의 상태, $S[1]$은 서쪽 셀의 상태, $S[2]$는 남쪽 셀의 상태, $S[3]$은 동쪽 셀의 상태, $S[4]$는 북쪽 셀의 상태이다.
2. Pulibot은 인식한 상태 배열에 대응하는 명령 $(Z, A)$를 정한다.
3. Pulibot은 명령을 수행한다. 먼저 셀 $(r,c)$의 색을 $Z$로 바꾸고, 그다음 동작 $A$를 한다. 동작은 셀 $(r,c)$에 머무르기, 인접한 4개의 셀 중 하나로 이동하기, 프로그램 종료하기 중 하나이다.

예를 들어, Pulibot이 색이 0인 셀 $(0,0)$에 있고 상태 배열 $S = [0, -2, 2, 2, -2]$를 인식했다고 하자. 이때 프로그램은 현재 셀의 색을 $Z = 1$로 바꾸고 동쪽으로 이동하도록 작성할 수 있다. 아래 그림을 참고하라.

로봇 대회 규칙

• 시작할 때 Pulibot은 셀 $(0,0)$에 놓이고 프로그램 실행을 시작한다.
• Pulibot은 빈 셀이 아닌 셀로 이동할 수 없다.
• Pulibot의 프로그램은 $500\,000$단계 이내에 종료해야 한다.
• 프로그램이 종료된 후 빈 셀들의 색은 다음 조건을 만족해야 한다. 셀 $(0,0)$에서 $(H-1,W-1)$까지의 최단 경로 중, 경로에 포함된 모든 셀의 색이 1인 경로가 존재한다. 그 밖의 빈 셀들의 색은 모두 0이다.
• Pulibot은 어느 빈 셀에서든 프로그램을 종료할 수 있다.

다음 그림은 $H = W = 6$인 미로의 한 예이다. 왼쪽은 시작 상태이고, 오른쪽은 종료 후 빈 셀들의 기대 색이다.

$Z_{MAX} = 19$. Pulibot은 0부터 19까지의 색을 사용할 수 있다.

Pulibot을 테스트하는 각 미로는 다음 조건을 만족한다.

• $2 \le H, W \le 15$
• 셀 $(0,0)$에서 셀 $(H-1,W-1)$까지 가는 경로가 적어도 하나 있다.