Background

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:

#include <vector>

void program_pulibot();
void set_instruction(std::vector<int> S, int Z, char A);

Problem Description

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.
2. Then, the Pulibot determines the instruction $(Z, A)$ corresponding to the recognized state array.
3. 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:

Input Format

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.

Output Format

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)
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.

Hint

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.
2. (10 points) $H = 2$.
3. (18 points) Between any two empty cells, there is exactly one path.
4. (20 points) The length of the shortest path from cell $(0,0)$ to cell $(H-1, W-1)$ is $H + W - 2$.
5. (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: <MSG> and terminates, where <MSG> 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