Robot Contest

문제

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

Pulibot will be tested on a maze consisting of a $(H+2)\times (W+2)(H+2)\; \backslash times\; (W+2)$ grid of cells. The rows of the grid are numbered from $-1-1$ to $HH$ from north to south and the columns of the grid are numbered from $-1-1$ to $WW$ from west to east. We refer to the cell located at row $rr$ and column $cc$ of the grid ($-1\le r\le H-1\; \backslash le\; r\; \backslash le\; H$, $-1\le c\le W-1\; \backslash le\; c\; \backslash le\; W$) as cell $(r,c)(r,\; c)$.

Consider a cell $(r,c)(r,c)$ such that $0\le r<H0\; \backslash le\; r\; \backslash lt\; H$ and $0\le c<W0\; \backslash le\; c\; \backslash lt\; W$. There are $44$ cells adjacent to cell $(r,c)(r,c)$:

• cell $(r,c-1)(r,c-1)$ is referred to as the cell west of cell $(r,c)(r,c)$;
• cell $(r+1,c)(r+1,c)$ is referred to as the cell south of cell $(r,c)(r,c)$;
• cell $(r,c+1)(r,c+1)$ is referred to as the cell east of cell $(r,c)(r,c)$;
• cell $(r-1,c)(r-1,c)$ is referred to as the cell north of cell $(r,c)(r,c)$.

Cell $(r,c)(r,c)$ is called a boundary cell of the maze if $r=-1r=-1$ or $r=Hr=H$ or $c=-1c=-1$ or $c=Wc=W$ holds. Each cell that is not a boundary cell of the maze is either an obstacle cell or an emptycell. Additionally, each empty cell has a color, represented by a nonnegative integer between $00$ and $Z_{MAX}Z\_\{MAX\}$, inclusive. Initially, the color of each empty cell is $00$.

For example, consider a maze with $H=4H=4$ and $W=5W=5$, containing a single obstacle cell $(1,3)(1,3)$:

The only obstacle cell is denoted by a cross. Boundary cells of the maze are shaded. The numbers written to each empty cell represent their respective colors.

A path of length $\mathrm{\ell }\backslash ell$ ($\mathrm{\ell }>0\backslash ell\; \backslash gt\; 0$) from cell $(r_0,c_0)(r\_0,\; c\_0)$ to cell $(r_{\mathrm{\ell }},c_{\mathrm{\ell }})(r\_\backslash ell,\; c\_\backslash ell)$ is a sequence of pairwise distinct *empty* cells $(r_0,c_0),(r_1,c_1),\dots ,(r_{\mathrm{\ell }},c_{\mathrm{\ell }})(r\_0,c\_0),\; (r\_1,\; c\_1),\; \backslash ldots,\; (r\_\backslash ell,\; c\_\backslash ell)$ in which for each $ii$ ($0\le i<\mathrm{\ell }0\; \backslash le\; i\; \backslash lt\; \backslash ell$) the cells $(r_i,c_i)(r\_i,\; c\_i)$ and $(r_{i+1},c_{i+1})(r\_\{i+1\},\; c\_\{i+1\})$ are adjacent.

Note that a path of length $\mathrm{\ell }\backslash ell$ contains exactly $\mathrm{\ell }+1\backslash ell+1$ cells.

At the contest, the researchers set up a maze in which there exists at least one path from cell $(0,0)(0,0)$ to cell $(H-1,W-1)(H-1,\; W-1)$. Note that this implies that cells $(0,0)(0,\; 0)$ and $(H-1,W-1)(H-1,\; W-1)$ are guaranteed to be empty.

Hanga does not know which cells of the maze are empty and which cells are obstacles.

Your task is to help Hanga to program Pulibot so that it is capable of finding a shortest path (that is, a path of minimum length) from cell $(0,0)(0,0)$ to cell $(H-1,W-1)(H-1,\; W-1)$ in the unknown maze set up by the researchers. The specification of Pulibot and the rules of the contest are described below.

Pulibot's Specification

Define the state of a cell $(r,c)(r,c)$ for each $-1\le r\le H-1\; \backslash le\; r\; \backslash le\; H$ and $-1\le c\le W-1\; \backslash le\; c\; \backslash le\; W$ as an integer so that:

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

Pulibot's program is executed as a sequence of steps. In each step, Pulibot recognizes the states of nearby cells and then performs an instruction. The instruction it performs is determined by the recognized states. A more precise description follows.

Suppose that at the beginning of the current step, Pulibot is at cell $(r,c)(r,c)$, which is an empty cell. The step is performed as follows:

1. First, Pulibot recognizes the current state array, that is, the array $S=[S[0],S[1],S[2],S[3],S[4]]S\; =\; [S[0],\; S[1],\; S[2],\; S[3],\; S[4]]$, consisting of the state of cell $(r,c)(r,c)$ and of all adjacent cells:
   • $S[0]S[0]$ is the state of cell $(r,c)(r,c)$.
   • $S[1]S[1]$ is the state of the cell to the west.
   • $S[2]S[2]$ is the state of the cell to the south.
   • $S[3]S[3]$ is the state of the cell to the east.
   • $S[4]S[4]$ is the state of the cell to the north.
2. Then, Pulibot determines the instruction $(Z,A)(Z,\; A)$ which corresponds to the recognized state array.
3. Finally, Pulibot performs that instruction: it sets the color of cell $(r,c)(r,\; c)$ to color $ZZ$ and then it performs action $AA$, which is one of the following actions:
   • stay at cell $(r,c)(r,c)$;
   • move to one of the $44$ adjacent cells;
   • terminate the program.

For example, consider the scenario displayed on the left of the following figure. Pulibot is currently at cell $(0,0)(0,\; 0)$ with the color $00$. Pulibot recognizes the state array $S=[0,-2,2,2,-2]S\; =\; [0,\; -2,\; 2,\; 2,\; -2]$. Pulibot may have a program which, upon recognizing this array, sets the color of the current cell to $Z=1Z\; =\; 1$ and then moves to the east, as displayed in the middle and on the right of the figure:

Robot Contest Rules

• At the start, Pulibot is placed at cell $(0,0)(0,0)$ and begins to execute its program.
• Pulibot is not allowed to move to a cell which is not empty.
• Pulibot's program must terminate after at most $500000500\backslash ,000$ steps.
• After the termination of Pulibot's program, empty cells in the maze should be colored such that:
  • There exists a shortest path from $(0,0)(0,0)$ to $(H-1,W-1)(H-1,\; W-1)$ for which the color of each cell included in the path is $11$.
  • The color of every other empty cell is $00$.
• Pulibot may terminate its program at any empty cell.

For example, the following figure shows a possible maze with $H=W=6H\; =\; W\; =\; 6$. The starting configuration is displayed on the left and the expected coloring of empty cells after termination is displayed on the right: