P9605 [IOI 2023] Robot Contest

This is an interactive problem. You only need to implement the functions required in the code. Your code does not need to include any additional header files, nor do you need to implement the `main` function. This problem only supports C++ submissions. --- Due to some technical reasons, you may need to add the following content at the beginning of your source code: ```cpp #include void program_pulibot(); void set_instruction(std::vector S, int Z, char A); ```

AI researchers at the University of Szeged are holding a robot programming contest. Your friend Hanga decided to participate. Since the famous Hungarian sheepdog breed Puli is very smart, the goal of the contest is to program a top-level Pulibot. The Pulibot will be tested in a maze consisting of an $(H+2) \times (W+2)$ grid. The rows of the grid are numbered from north to south as $-1$ to $H$, and the columns are numbered from west to east as $-1$ to $W$. We call the cell in row $r$ and column $c$ ($-1 \le r \le H$, $-1 \le c \le W$) cell $(r,c)$. Consider a cell $(r,c)$ ($0 \le r \lt H$, $0 \le c \lt W$). It has $4$ **adjacent** cells: * Cell $(r,c-1)$ is called the **west neighbor** of cell $(r,c)$. * Cell $(r+1,c)$ is called the **south neighbor** of cell $(r,c)$. * Cell $(r,c+1)$ is called the **east neighbor** of cell $(r,c)$. * Cell $(r-1,c)$ is called the **north neighbor** of cell $(r,c)$. If $r=-1$ or $r=H$ or $c=-1$ or $c=W$ holds, then cell $(r,c)$ is called the **boundary** of the maze. Each cell that is not on the boundary of the maze is either an **obstacle** or **empty**. In addition, each empty cell has a **color**, represented by a non-negative integer between $0$ and $Z_{\text{MAX}}$, including $0$ and $Z_{\text{MAX}}$. Initially, the color of each empty cell is $0$. For example, consider a maze with $H=4$, $W=5$, containing one obstacle cell $(1,3)$.  The only obstacle cell is marked with $\times$. Boundary cells of the maze are shaded. The number in each empty cell indicates its color. A **path** of length $\ell$ ($\ell\gt 0$) from cell $(r_0, c_0)$ to cell $(r_\ell, c_\ell)$ is a sequence of **empty** cells $(r_0,c_0), (r_1, c_1), \ldots, (r_\ell, c_\ell)$, where all empty cells in the sequence are pairwise distinct. For each $i$ ($0\le i\lt\ell$), cells $(r_i, c_i)$ and $(r_{i+1}, c_{i+1})$ are adjacent. Note that a path of length $\ell$ contains exactly $\ell+1$ cells. In the contest, the researchers prepared a maze in which there is at least one path from cell $(0,0)$ to cell $(H-1, W-1)$. Note that this means cells $(0,0)$ and $(H-1, W-1)$ are guaranteed to be empty. Hanga does not know which cells in the maze are empty and which are obstacles. Your task is to help Hanga program the Pulibot so that it can find a **shortest path** (i.e. a path of minimum length) from cell $(0,0)$ to cell $(H-1, W-1)$ in the unknown maze prepared by the researchers. The Pulibot specification and contest rules are described below. Note that the last part of the statement describes a display tool that can be used to visualize the Pulibot. ### Pulibot Specification For each cell $(r,c)$ ($-1 \le r \le H$, $-1 \le c \le W$), its **state** is defined as an integer as follows: * If cell $(r,c)$ is a boundary cell, then its state is $-2$. * If cell $(r,c)$ is an obstacle, then its state is $-1$. * If cell $(r,c)$ is empty, then its state is the color of the cell. The Pulibot program is executed step by step. In each step, the Pulibot recognizes the states of nearby cells and then executes one instruction. The instruction it executes depends on the recognized states. A more precise description follows. Suppose that at the beginning of the current step, the Pulibot is in cell $(r,c)$, which is an empty cell. The step is performed as follows: 1. First, the Pulibot recognizes the current **state array**, i.e. the array $S = [S[0], S[1], S[2], S[3], S[4]]$, which contains the states of cell $(r,c)$ and all its adjacent cells: * $S[0]$ is the state of cell $(r,c)$. * $S[1]$ is the state of the west neighbor. * $S[2]$ is the state of the south neighbor. * $S[3]$ is the state of the east neighbor. * $S[4]$ is the state of the north neighbor. 1. Then, the Pulibot determines the **instruction** $(Z, A)$ corresponding to the recognized state array. 1. Finally, the Pulibot executes this instruction: it sets the color of cell $(r,c)$ to $Z$, and then performs action $A$, where $A$ is one of the following: * **Stay** in cell $(r,c)$. * **Move** to one of the $4$ neighboring cells. * **Terminate the program**. For example, consider the situation shown on the left in the figure below. The Pulibot is currently in cell $(0,0)$, with color $0$. The Pulibot recognizes the state array $S=[0, -2, 2, 2, -2]$. The Pulibot may have a program that, based on the recognized array, sets the color of the current cell to $Z=1$, and then moves east, as shown in the middle and right parts of the figure:  ### Robot Contest Rules * At the start, the Pulibot is placed in cell $(0,0)$ and begins executing its program. * The Pulibot is not allowed to move to a non-empty cell. * The Pulibot program must terminate after at most $500\,000$ steps. * After the Pulibot program terminates, the coloring of empty cells in the maze satisfies the following: - There exists a shortest path from $(0,0)$ to $(H-1, W-1)$ such that the color of every cell on the path is $1$. - All other empty cells have color $0$. * The Pulibot may terminate its program in any empty cell. For example, the figure below shows a possible maze with $H=W=6$. The left side shows the initial configuration, and the right side shows one acceptable coloring of the empty cells after the program terminates: 

You need to implement the following function: ``` void program_pulibot() ``` * This function should generate the Pulibot program. The program should work correctly for all values of $H$ and $W$ and for any maze that satisfies the constraints. * For each test case, this function is called only once. This function may call the following function to generate the Pulibot program: ``` void set_instruction(int[] S, int Z, char A) ``` * $S$: an array of length $5$, used to describe the state array. * $Z$: a non-negative integer representing a color. * $A$: a single character representing the Pulibot action, as follows: - `H`: stay. - `W`: move to the west neighbor. - `S`: move to the south neighbor. - `E`: move to the east neighbor. - `N`: move to the north neighbor. - `T`: terminate the program. * Calling this function instructs the Pulibot which instruction $(Z, A)$ it should execute when it recognizes the state array $S$. Calling this function multiple times with the same state array $S$ will result in `Output isn't correct`. You do not need to call `set_instruction` for every possible state array $S$. However, if the Pulibot later recognizes a state array for which no instruction was set, you will get `Output isn't correct`. After `program_pulibot` finishes, the grader will run the Pulibot program on one or more mazes. These runs are **not** counted toward the time limit of your solution. The grader is **not** adaptive, i.e. the set of mazes for each test case is fixed in advance. If the Pulibot violates any of the robot contest rules before terminating its program, you will get `Output isn't correct`.

The function `program_pulibot` may call `set_instruction` as follows: Call | Instruction for the corresponding state array $S$ :-------------------------------------------:|:---------------------------------------: `set_instruction([0, -2, -1, 0, -2], 1, E)` | Color $1$ and move east. `set_instruction([0, 1, -1, 0, -2], 1, E)` | Color $1$ and move east. `set_instruction([0, 1, 0, -2, -2], 1, S)` | Color $1$ and move south. `set_instruction([0, -1, -2, -2, 1], 1, T)` | Color $1$ and terminate the program. Consider a setting with $H=2$, $W=3$, and the maze shown below.  For this particular maze, the Pulibot program runs in four steps. The state arrays recognized by the Pulibot and the instructions it executes correspond exactly, in order, to the four calls to `set_instruction` above. The last of these instructions terminates the program. The figure below shows the maze before each of the four steps, and the final colors after termination.  However, note that this program of $4$ instructions may fail to find a shortest path in other valid mazes. Therefore, if this program is submitted, it will receive `Output isn't correct`.

## Constraints $Z_{\text{MAX}} = 19$. Therefore, the Pulibot can use colors from $0$ to $19$, including $0$ and $19$. For each maze used to test the Pulibot: * $2 \le H, W \le 15$. * There is at least one path from cell $(0,0)$ to cell $(H-1, W-1)$. ## Subtasks 1. (6 points) The maze has no obstacle cells. 1. (10 points) $H = 2$. 1. (18 points) Between any two empty cells, there is exactly one path. 1. (20 points) The length of the shortest path from cell $(0,0)$ to cell $(H-1, W-1)$ is $H + W - 2$. 1. (46 points) No additional constraints. If, in any test case, the calls to `set_instruction` or the execution of the Pulibot program do not satisfy the restrictions described in “Implementation Details”, then the score of the solution for that subtask will be $0$. In each subtask, you can obtain partial points by generating an almost correct coloring. Formally: * If the final colors of empty cells satisfy the robot contest rules, then the solution for the test case is **full**. * If the final coloring is as follows, then the solution for the test case is **partial**: - There exists a shortest path from $(0,0)$ to $(H-1, W-1)$ such that the color of every cell on the path is $1$. - There are no other empty cells with color $1$ in the grid. - Some empty cells in the grid have colors that are neither $0$ nor $1$. If your solution for a test case is neither full nor partial, then the score for that test case is $0$. In subtasks 1-4, for each test case, a full solution is worth 100% of the subtask points, and a partial solution is worth 50% of the subtask points. In subtask 5, your score depends on the number of colors used in the Pulibot program. More precisely, let $Z^\star$ be the maximum value of $Z$ among all calls to `set_instruction`. The score for a test case is computed according to the table below: | Condition | Score (full) | Score (partial) | |:-----------------------:|:---------------------:|:---------------------:| | $11 \le Z^\star \le 19$ | $20 + (19 - Z^\star)$ | $12 + (19 - Z^\star)$ | | $Z^\star = 10$ | $31$ | $23$ | | $Z^\star = 9$ | $34$ | $26$ | | $Z^\star = 8$ | $38$ | $29$ | | $Z^\star = 7$ | $42$ | $32$ | | $Z^\star \le 6$ | $46$ | $36$ | The score of each subtask is the minimum score among all test cases in that subtask. ## Sample Grader The sample grader reads input in the following format: * Line $1$: $H \; W$. * Line $2 + r$ ($0 \le r \lt H$): $m[r][0] \; m[r][1] \; \ldots \; m[r][W-1]$. Here, $m$ is a 2D integer array with $H$ rows and $W$ columns, describing the non-boundary cells of the maze. If cell $(r, c)$ is empty, then $m[r][c] = 0$. If cell $(r, c)$ is an obstacle, then $m[r][c] = 1$. The sample grader first calls `program_pulibot()`. If the sample grader detects any rule violation, it prints `Protocol Violation: ` and terminates, where `` is one of the following error messages: * `Invalid array`: $-2 \le S[i] \le Z_{\text{MAX}}$ does not hold for some $i$, or the length of $S$ is not $5$. * `Invalid color`: $0 \le Z \le Z_{\text{MAX}}$ does not hold. * `Invalid action`: the character $A$ is not one of `H`, `W`, `S`, `E`, `N`, `T`. * `Same state array`: `set_instruction` was called two or more times with the same $S$. Otherwise, when `program_pulibot` finishes, the sample grader runs the Pulibot program in the maze described by the input. The sample grader produces two outputs. First, it writes a log of Pulibot actions into the file `robot.bin` in the working directory. This file is used as input for the visualization tool described in the next section. Second, if the Pulibot program does not terminate successfully, the sample grader prints one of the following error messages: * `Unexpected state`: the Pulibot recognized a state array for which `set_instruction` was not called. * `Invalid move`: an action was executed that caused the Pulibot to move to a non-empty cell. * `Too many steps`: the Pulibot executed $500\,000$ steps without terminating. Otherwise, let $e[r][c]$ be the state of cell $(r, c)$ after the Pulibot program terminates. The sample grader prints $H$ lines in the following format: * Line $1 + r$ ($0 \le r \lt H$): $e[r][0] \; e[r][1] \; \ldots \; e[r][W-1]$. ## Display Tool The attachments for this task include a file named `display.py`. When called, this Python script displays the Pulibot's actions in the maze described by the sample grader input. To do so, the working directory must contain the binary file `robot.bin`. To call the script, run the following command. ``` python3 display.py ``` A simple GUI will appear, with the following main features: * You can observe the state of the entire maze. The current position of the Pulibot is highlighted with a rectangle. * You can browse the Pulibot steps by clicking the arrow buttons or using hotkeys. You can also jump to a specific step. * The next step to be executed by the Pulibot program is shown at the bottom. It shows the current state array and the instruction to be executed. After the last step, it will either show one of the grader error messages, or show `Terminated` if the program terminated successfully. * For each number representing a color, you can specify the background color and the displayed text. The displayed text is a short string that should appear in each cell with that color. You can specify the background color and displayed text in either of the following ways: - Set them in a dialog window after clicking the `Colors` button. - Edit the contents of the `colors.txt` file. * To reload `robot.bin`, use the `Reload` button. This can be used when the contents of `robot.bin` change. Translated by ChatGPT 5