Robot Contest

AI researchers at the University of Szeged are holding a robot programming contest. Your friend, Hanga, has decided to take part. The goal is to program the ultimate Pulibot, modeled on the intelligence of the Puli, a famous Hungarian herding dog breed.

Pulibot is tested on a maze made of a $(H+2) \times (W+2)$ grid of cells. Rows are numbered $-1$ to $H$ from north to south, and columns are numbered $-1$ to $W$ from west to east. Cell $(r,c)$ is the cell in row $r$ and column $c$, where $-1 \le r \le H$ and $-1 \le c \le W$.

For a cell $(r,c)$ with $0 \le r < H$ and $0 \le c < W$, the four adjacent cells are the west cell $(r,c-1)$, the south cell $(r+1,c)$, the east cell $(r,c+1)$, and the north cell $(r-1,c)$.

Cell $(r,c)$ is a boundary cell if $r=-1$, $r=H$, $c=-1$, or $c=W$. Every other cell is either an obstacle or an empty cell. Each empty cell has a color, an integer from $0$ to $Z_{MAX}$ inclusive. Initially, every empty cell has color $0$.

For example, the maze below has $H=4$ and $W=5$ and one obstacle at cell $(1,3)$. The obstacle is marked with a cross, boundary cells are shaded, and the numbers show the colors of the empty cells.

A path of length $\ell$ ($\ell > 0$) from cell $(r_0,c_0)$ to cell $(r_\ell,c_\ell)$ is a sequence of pairwise distinct empty cells $(r_0,c_0), (r_1,c_1), \ldots, (r_\ell,c_\ell)$ where each pair of consecutive cells is adjacent. A path of length $\ell$ contains exactly $\ell+1$ cells.

The researchers set up a maze where at least one path exists from cell $(0,0)$ to cell $(H-1,W-1)$. Cells $(0,0)$ and $(H-1,W-1)$ are therefore empty.

Hanga does not know which cells are empty and which are obstacles. Her task is to program Pulibot so that it finds a shortest path (a path of minimum length) from cell $(0,0)$ to cell $(H-1,W-1)$ in the unknown maze. The specification and the contest rules follow.

Pulibot's Specification

The state of a cell $(r,c)$, for $-1 \le r \le H$ and $-1 \le c \le W$, is an integer defined as follows:

• If cell $(r,c)$ is a boundary cell, its state is $-2$.
• If cell $(r,c)$ is an obstacle cell, its state is $-1$.
• If cell $(r,c)$ is an empty cell, its state is the color of the cell.

Pulibot's program runs as a sequence of steps. In each step, Pulibot reads the states of nearby cells, then performs an instruction chosen by those states.

Suppose Pulibot is at empty cell $(r,c)$ at the start of a step. The step proceeds as follows.

1. Pulibot reads the state array $S = [S[0], S[1], S[2], S[3], S[4]]$. $S[0]$ is the state of cell $(r,c)$, $S[1]$ is the state of the west cell, $S[2]$ is the state of the south cell, $S[3]$ is the state of the east cell, and $S[4]$ is the state of the north cell.
2. Pulibot determines the instruction $(Z, A)$ that matches the state array.
3. Pulibot sets the color of cell $(r,c)$ to $Z$, then performs action $A$. The action is one of the following: stay at cell $(r,c)$, move to one of the 4 adjacent cells, or terminate the program.

For example, suppose Pulibot is at cell $(0,0)$ with color $0$ and reads $S = [0, -2, 2, 2, -2]$. Its program may set the color of the current cell to $Z = 1$ and then move east, as shown in the figures below.

Robot Contest Rules

• At the start, Pulibot is placed at cell $(0,0)$ and begins executing its program.
• Pulibot may not move to a cell that is not empty.
• Pulibot's program must terminate within $500\,000$ steps.
• After the program terminates, the empty cells must satisfy the following. There exists a shortest path from $(0,0)$ to $(H-1,W-1)$ in which every cell on the path has color $1$. Every other empty cell has color $0$.
• Pulibot may terminate its program at any empty cell.

The figure below shows a possible maze with $H = W = 6$. The left side shows the starting configuration, and the right side shows the expected coloring after termination.

$Z_{MAX} = 19$. Pulibot can use colors from $0$ to $19$, inclusive.

For each maze used to test Pulibot:

• $2 \le H, W \le 15$
• There is at least one path from cell $(0,0)$ to cell $(H-1,W-1)$.