robot (IOI contest)
Time limit: 1 seconds | Memory limit: 2048 MB | Task type: interactive
Algorithms: bfs, graph theory, constructive, ad-hoc, tree, implementation, graph traversal

# 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)$ grid of cells.
The rows of the grid are numbered from $-1$ to $H$ from north to south and the columns of the grid are numbered from $-1$ to $W$ from west to east.
We refer to the cell located at row $r$ and column $c$ of the grid ($-1 \le r \le H$, $-1 \le c \le W$) as cell $(r, c)$.

Consider a cell $(r,c)$ such that $0 \le r \lt H$ and $0 \le c \lt W$. There are $4$ cells **adjacent** to cell $(r,c)$:
* cell $(r,c-1)$ is referred to as the cell **west** of cell $(r,c)$;
* cell $(r+1,c)$ is referred to as the cell **south** of cell $(r,c)$;
* cell $(r,c+1)$ is referred to as the cell **east** of cell $(r,c)$;
* cell $(r-1,c)$ is referred to as the cell **north** of cell $(r,c)$.

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

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

![Numbering](robot-numbering.png "250")

The only obstacle cell is denoted by a cross. Boundary cells of the maze are shaded.
The number in each empty cell represents 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 pairwise distinct *empty* cells $(r_0,c_0), (r_1, c_1), \ldots, (r_\ell, c_\ell)$ 
in which for each $i$ ($0 \le i \lt \ell$) the 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.

At the contest, the researchers set up a maze in which there exists at least one path from cell $(0,0)$ to cell $(H-1, W-1)$. 
Note that this implies that cells $(0, 0)$ and $(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)$ to cell $(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.

Note that the last section of this problem statement describes a display tool you can use to visualize Pulibot.

### Pulibot's Specification

Define the **state** of a cell $(r,c)$ for each $-1 \le r \le H$ and $-1 \le c \le W$ as an integer so that:
* if cell $(r,c)$ is a boundary cell then its state is $-2$;
* if cell $(r,c)$ is an obstacle cell then its state is $-1$;
* if cell $(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)$, 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]]$, consisting of the state of cell $(r,c)$ and of all adjacent cells:
    * $S[0]$ is the state of cell $(r,c)$.
    * $S[1]$ is the state of the cell to the west.
    * $S[2]$ is the state of the cell to the south.
    * $S[3]$ is the state of the cell to the east.
    * $S[4]$ is the state of the cell to the north.
1. Then, Pulibot determines the **instruction** $(Z, A)$ which corresponds to the recognized state array.
1. Finally, Pulibot performs that instruction: it sets the color of cell $(r, c)$ to color $Z$
and then it performs action $A$, which is one of the following actions:
    * *stay* at cell $(r,c)$;
    * *move* to one of the $4$ 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)$ with the color $0$.
Pulibot recognizes the state array $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 = 1$ and then moves to the east,
as displayed in the middle and on the right of the figure:

![Actions of a step of Pulibot](robot-actions.png "700")

### Robot Contest Rules

* At the start, Pulibot is placed at cell $(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 $500\,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)$ to $(H-1, W-1)$ for which the color of each cell included in the path is $1$.
  - All other empty cells have color $0$.
* Pulibot may terminate its program at any empty cell.
  
For example, the following figure shows a possible maze with $H = W = 6$.
The starting configuration is displayed on the left and one acceptable coloring of empty cells after termination is displayed on the right:

![Shortest path](robot-shortest-path.png "500")


## Implementation Details

You should implement the following procedure.

```
void program_pulibot()
```

* This procedure should produce Pulibot's program. This program should work correctly for all values of $H$ and $W$ and any maze which meets the task constraints.
* This procedure is called exactly once for each test case.

This procedure can make calls to the following procedure to produce Pulibot's program:

```
void set_instruction(int[] S, int Z, char A)
```

* $S$: array of length $5$ describing a state array.
* $Z$: a nonnegative integer representing a color.
* $A$: a single character representing an action of Pulibot as follows:
    - `H`: stay;
    - `W`: move to the west;
    - `S`: move to the south;
    - `E`: move to the east;
    - `N`: move to the north;
    - `T`: terminate the program.
* Calling this procedure instructs Pulibot that upon recognizing the state array $S$ it should perform the instruction $(Z, A)$.

Сalling this procedure multiple times with the same state array $S$ will result in an `Output isn't correct` verdict.

It is not required to call `set_instruction` with each possible state array $S$. However, if Pulibot later recognizes a state array for which an instruction was not set, you will get an `Output isn't correct` verdict.

After `program_pulibot` completes, the grader invokes Pulibot's program over one or more mazes.
These invocations do *not* count towards the time limit for your solution.
The grader is *not* adaptive, that is, the set of mazes is predefined in each test case.

If Pulibot violates any of the Robot Contest Rules before terminating its program, you will get an `Output isn't correct` verdict.

## Example

The procedure `program_pulibot` may make calls to `set_instruction` as follows:

Call                                         | Instruction for state array $S$
:-------------------------------------------:|:---------------------------------------:
`set_instruction([0, -2, -1, 0, -2], 1, E)`  | Set color to $1$ and move east
`set_instruction([0, 1, -1, 0, -2], 1, E)`   | Set color to $1$ and move east
`set_instruction([0, 1, 0, -2, -2], 1, S)`   | Set color to $1$ and move south
`set_instruction([0, -1, -2, -2, 1], 1, T)`  | Set color to $1$ and terminate program

Consider a scenario where $H=2$ and $W=3$, and the maze is displayed in the following figure.

![Example maze](robot-example-maze.png "200")

For this particular maze Pulibot's program runs in four steps. The state arrays Pulibot recognizes 
and the instructions it performs correspond exactly to the four calls to `set_instruction` made
above, in order. The last of these instructions terminates the program.

The following figure shows the maze before each of the four steps and the final colors after termination.

![Example simulation](robot-example-steps.png "500")

However, do note that this program of $4$ instructions might not find a shortest path in other valid mazes.
Therefore, if submitted, it will receive an `Output isn't correct` verdict.

## Constraints

$Z_{MAX} = 19$. Hence, 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)$. 

## Subtasks

1. (6 points) There is no obstacle cell in the maze.
1. (10 points) $H = 2$
1. (18 points) There is exactly one path between each pair of empty cells.
1. (20 points) Each shortest path from cell $(0,0)$ to cell $(H-1, W-1)$ has length $H + W - 2$.
1. (46 points) No additional constraints.

If, in any of the test cases, the calls to the procedure `set_instruction` or Pulibot's program over its execution do not conform to the constraints described in Implementation Details, the score of your solution for that subtask will be $0$.

In each subtask, you can obtain a partial score by producing a coloring that is almost correct.

Formally:
* The solution of a test case is **complete** if the final coloring of the empty cells satisfies Robot Contest Rules.
* The solution of a test case is **partial** if the final coloring looks as follows:
  - There exists a shortest path from $(0,0)$ to $(H-1, W-1)$ for which the color of each cell included in the path is $1$.
  - There is no other empty cell in the grid with color $1$.
  - Some empty cell in the grid has a color other than $0$ and $1$.

If your solution to a test case is neither complete nor partial, your score for the corresponding
test case will be $0$.

In subtasks 1-4, the score for a complete solution is 100% and the score for a partial solution to a test case is 50% of the points for its subtask.

In subtask 5, your score depends on the number of colors used in Pulibot's program.
More precisely, denote by $Z^\star$ the maximum value of $Z$ over all calls made to `set_instruction`.
The score of the test case is calculated according to the following table:

| Condition               | Score (complete)      | 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 for each subtask is the minimum of the points for the test cases in the subtask.

## Sample Grader

The sample grader reads the 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 an array of $H$ arrays of $W$ integers, describing the non-boundary cells of the maze.
$m[r][c] = 0$ if cell $(r, c)$ is an empty cell and $m[r][c] = 1$ if cell $(r, c)$ is an obstacle cell.

<!-- IMPORTANT NOTE TO TRANSLATORS: THE FOLLOWING MESSAGES (IN BACKTICKS) SHOULD NOT BE TRANSLATED -->

The sample grader first calls `program_pulibot()`.
If the sample grader detects a protocol violation, the sample grader prints
`Protocol Violation: <MSG>` and terminates, where `<MSG>` is one of the following error messages:

* `Invalid array`: $-2 \le S[i] \le Z_{MAX}$ is not met for some $i$ or the length of $S$ is not $5$.
* `Invalid color`: $0 \le Z \le Z_{MAX}$ is not met.
* `Invalid action`: character $A$ is not one of `H`, `W`, `S`, `E`, `N` or `T`. 
* `Same state array`: `set_instruction` was called with the same array $S$ at least twice.

Otherwise, when `program_pulibot` completes, the sample grader executes Pulibot's program in the maze described by the input.

The sample grader produces two outputs.

First, the sample grader writes a log of Pulibot's actions to the file `robot.bin` in the working directory.
This file serves as the input of the visualization tool described in the following section.

Second, if Pulibot's program does not terminate successfully, the sample grader prints one of the following error messages:

* `Unexpected state`: Pulibot recognized a state array which `set_instruction` was not called with.
* `Invalid move`: performing an action resulted in Pulibot moving to a nonempty cell.
* `Too many steps`: Pulibot performed $500\,000$ steps without terminating its program.

Otherwise, let $e[r][c]$ be the state of cell $(r, c)$ after Pulibot’s 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 attachment package for this task contains a file named `display.py`.
When invoked, this Python script displays Pulibot's actions in the maze described by the input of the sample grader.
For this, the binary file `robot.bin` must be present in the working directory.

To invoke the script, execute the following command.
```
python3 display.py
```

A simple graphical interface shows up. The main features are as follows:

* You can observe the status of the full maze. The current location of Pulibot is highlighted by a rectangle.
* You can browse through the steps of Pulibot by clicking the arrow buttons or pressing their hotkeys. You can also jump to a specific step.
* The upcoming step in Pulibot's program is shown at the bottom.
It shows the current state array and the instruction it will perform.
After the final step, it shows either one of the error messages of the grader, or `Terminated` if the program successfully terminates.
* To each number that represents a color, you can assign a visual background color, as well as a display text. The display text is a short string that shall appear in each cell having that color. You can assign background colors and display texts in either of the following ways:
  - Set them in a dialog window after clicking on the `Colors` button.
  - Edit the contents of the `colors.txt` file.
* To reload `robot.bin`, use the `Reload` button. It is useful if the contents of `robot.bin` have changed.


Starter code:
grader.cpp: #include "robot.h"
#include <cassert>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>

static const int MAX_COLOR = 19;
static const int MAX_STATE = 5153632; // = (MAX_COLOR + 3) ^ 5
static const int MAX_STEPS = 500000;

static std::ofstream output;

[[noreturn]] static void die(const std::string &message)
{
    std::cout << message << "\n";
    output.close();
    exit(0);
}

[[noreturn]] static void pv(const std::string &message)
{
    die("Protocol Violation: " + message);
}

static int encode_state(const std::vector<int> &S)
{
    int state = 0;
    for (int s : S)
    {
        state = (MAX_COLOR + 3) * state + s + 2;
    }
    return state;
}

struct instruction
{
    char color;
    char action;
};

static int encode_instr(instruction instr)
{
    if (!instr.action)
    {
        return 0;
    }
    int index = std::string("HWSENT").find_first_of(instr.action) + 1;
    return (index << 5) | instr.color;
}

static instruction program[MAX_STATE];

void set_instruction(std::vector<int> S, int Z, char A)
{
    if (S.size() != 5)
    {
        pv("Invalid array");
    }
    for (int s : S)
    {
        if (s < -2 || s > MAX_COLOR)
        {
            pv("Invalid array");
        }
    }
    if (Z < 0 || Z > MAX_COLOR)
    {
        pv("Invalid color");
    }
    if (std::string("HWSENT").find_first_of(A) == std::string::npos)
    {
        pv("Invalid action");
    }
    int code = encode_state(S);
    if (program[code].action)
    {
        pv("Same state array");
    }
    program[code].color = Z;
    program[code].action = A;
}

static std::vector<std::vector<int>> cells;
static int H, W;
static int rx = 1, ry = 1;

static bool step(instruction instr)
{
    cells[rx][ry] = instr.color;
    switch (instr.action)
    {
    case 'H':
        break;
    case 'W':
        ry--;
        break;
    case 'S':
        rx++;
        break;
    case 'E':
        ry++;
        break;
    case 'N':
        rx--;
        break;
    case 'T':
        return true;
    }
    if (cells[rx][ry] < 0)
    {
        die("Invalid move");
    }
    return false;
}

int main()
{
    std::string line;
    std::getline(std::cin, line);
    std::istringstream line_ss(line);
    assert((line_ss >> H >> W) && (line_ss >> std::ws).eof());
    cells.resize(H + 2, std::vector<int>(W + 2));
    for (int j = 0; j <= W + 1; j++)
    {
        cells[0][j] = cells[H + 1][j] = -2;
    }
    for (int i = 1; i <= H; i++)
    {
        cells[i][0] = cells[i][W + 1] = -2;
        std::getline(std::cin, line);
        line_ss.str(line);
        line_ss.clear();
        for (int j = 1; j <= W; j++)
        {
            bool cell;
            line_ss >> cell;
            cells[i][j] = cell ? -1 : 0;
        }
        assert(line_ss && (line_ss >> std::ws).eof());
    }
    program_pulibot();
    output.open("robot.bin", std::ios::binary);
    output.put(H).put(W);
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            output.put(cells[i][j]);
        }
    }
    bool done = false;
    int steps = 0;
    while (!done && ++steps <= MAX_STEPS)
    {
        std::vector<int> state = {
            cells[rx][ry],
            cells[rx][ry - 1],
            cells[rx + 1][ry],
            cells[rx][ry + 1],
            cells[rx - 1][ry]};
        instruction instr = program[encode_state(state)];
        output.put(encode_instr(instr));
        if (!instr.action)
        {
            die("Unexpected state");
        }
        done = step(instr);
    }
    if (!done)
    {
        output.put(0xE0);
        die("Too many steps");
    }
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            std::cout << std::setw(2) << cells[i][j] << (j == W ? "\n" : " ");
        }
    }
}

robot.h: #include <vector>

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

robot.cpp: #include "robot.h"

void program_pulibot()
{
    set_instruction({0, -2, -1, 0, -2}, 1, 'E');
    set_instruction({0, 1, -1, 0, -2}, 1, 'E');
    set_instruction({0, 1, 0, -2, -2}, 1, 'S');
    set_instruction({0, -1, -2, -2, 1}, 1, 'T');
}


Grader code:
grader.cpp: #include "robot.h"
#include <cassert>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>

static const int MAX_COLOR = 19;
static const int MAX_STATE = 5153632; // = (MAX_COLOR + 3) ^ 5
static const int MAX_STEPS = 500000;

static std::ofstream output;

[[noreturn]] static void die(const std::string &message)
{
    std::cout << message << "\n";
    output.close();
    exit(0);
}

[[noreturn]] static void pv(const std::string &message)
{
    die("Protocol Violation: " + message);
}

static int encode_state(const std::vector<int> &S)
{
    int state = 0;
    for (int s : S)
    {
        state = (MAX_COLOR + 3) * state + s + 2;
    }
    return state;
}

struct instruction
{
    char color;
    char action;
};

static int encode_instr(instruction instr)
{
    if (!instr.action)
    {
        return 0;
    }
    int index = std::string("HWSENT").find_first_of(instr.action) + 1;
    return (index << 5) | instr.color;
}

static instruction program[MAX_STATE];

void set_instruction(std::vector<int> S, int Z, char A)
{
    if (S.size() != 5)
    {
        pv("Invalid array");
    }
    for (int s : S)
    {
        if (s < -2 || s > MAX_COLOR)
        {
            pv("Invalid array");
        }
    }
    if (Z < 0 || Z > MAX_COLOR)
    {
        pv("Invalid color");
    }
    if (std::string("HWSENT").find_first_of(A) == std::string::npos)
    {
        pv("Invalid action");
    }
    int code = encode_state(S);
    if (program[code].action)
    {
        pv("Same state array");
    }
    program[code].color = Z;
    program[code].action = A;
}

static std::vector<std::vector<int>> cells;
static int H, W;
static int rx = 1, ry = 1;

static bool step(instruction instr)
{
    cells[rx][ry] = instr.color;
    switch (instr.action)
    {
    case 'H':
        break;
    case 'W':
        ry--;
        break;
    case 'S':
        rx++;
        break;
    case 'E':
        ry++;
        break;
    case 'N':
        rx--;
        break;
    case 'T':
        return true;
    }
    if (cells[rx][ry] < 0)
    {
        die("Invalid move");
    }
    return false;
}

int main()
{
    std::string line;
    std::getline(std::cin, line);
    std::istringstream line_ss(line);
    assert((line_ss >> H >> W) && (line_ss >> std::ws).eof());
    cells.resize(H + 2, std::vector<int>(W + 2));
    for (int j = 0; j <= W + 1; j++)
    {
        cells[0][j] = cells[H + 1][j] = -2;
    }
    for (int i = 1; i <= H; i++)
    {
        cells[i][0] = cells[i][W + 1] = -2;
        std::getline(std::cin, line);
        line_ss.str(line);
        line_ss.clear();
        for (int j = 1; j <= W; j++)
        {
            bool cell;
            line_ss >> cell;
            cells[i][j] = cell ? -1 : 0;
        }
        assert(line_ss && (line_ss >> std::ws).eof());
    }
    program_pulibot();
    output.open("robot.bin", std::ios::binary);
    output.put(H).put(W);
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            output.put(cells[i][j]);
        }
    }
    bool done = false;
    int steps = 0;
    while (!done && ++steps <= MAX_STEPS)
    {
        std::vector<int> state = {
            cells[rx][ry],
            cells[rx][ry - 1],
            cells[rx + 1][ry],
            cells[rx][ry + 1],
            cells[rx - 1][ry]};
        instruction instr = program[encode_state(state)];
        output.put(encode_instr(instr));
        if (!instr.action)
        {
            die("Unexpected state");
        }
        done = step(instr);
    }
    if (!done)
    {
        output.put(0xE0);
        die("Too many steps");
    }
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            std::cout << std::setw(2) << cells[i][j] << (j == W ? "\n" : " ");
        }
    }
}

robot.h: #include <vector>

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

manager.cpp: #include <cassert>
#include <cinttypes>
#include <csignal>
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include "testlib.h"

const int MAX_COLOR = 19;
const int MAX_STATE = 5153632; // = (MAX_COLOR + 3) ^ 5
const int MAX_STEPS = 500000;

const std::string output_secret = "p71c1rw3EvfjFcMVWG0EOedGbWDX5uUp";

// Each instruction is encoded as a byte.
// The value zero indicates an unset instruction.
// Otherwise, the lowest 5 bits are the color, the highest 3 are the action.
// See the functions 'action' and 'color'.

using instruction = uint8_t;
instruction program[MAX_STATE];

char action(instruction instr)
{
    return "_HWSENT_"[instr >> 5];
}

int color(instruction instr)
{
    return instr & 0x1F;
}

void validate_instr(instruction instr)
{
    if (instr && (color(instr) > MAX_COLOR || action(instr) == '_'))
    {
        quit(_pv, "Invalid instruction");
    }
}

int encode_state(const std::vector<int> &S)
{
    int state = 0;
    for (int s : S)
    {
        state = (MAX_COLOR + 3) * state + s + 2;
    }
    return state;
}

std::string print_state(const std::vector<int> &S)
{
    std::string s = "[" + std::to_string(S[0]);
    for (int i = 1; i <= 4; i++)
    {
        s += ", ";
        s += std::to_string(S[i]);
    }
    s += "]";
    return s;
}

int H, W;

struct sim_state
{
    std::vector<std::vector<int>> cells;
    int rx = 1, ry = 1;

    bool step()
    {
        std::vector<int> state = {
            cells[rx][ry],
            cells[rx][ry - 1],
            cells[rx + 1][ry],
            cells[rx][ry + 1],
            cells[rx - 1][ry]};
        uint8_t instr = program[encode_state(state)];
        if (!instr)
        {
            quit(_wa, "Unexpected state: " + print_state(state));
        }
        cells[rx][ry] = color(instr);
        switch (action(instr))
        {
        case 'T':
            return true;
        case 'W':
            ry--;
            break;
        case 'S':
            rx++;
            break;
        case 'E':
            ry++;
            break;
        case 'N':
            rx--;
            break;
        case 'H':
            break;
        default:
            quit(_fail, "Unknown action");
        }
        if (cells[rx][ry] < 0)
        {
            quit(_wa, "Invalid move: S = " + print_state(state) +
                          ", A = '" + action(instr) + "'");
        }
        return false;
    }
};

const std::vector<std::pair<int, int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

// This is not necessary, but it gives better error messages
static void check_path(const std::vector<std::vector<int>> &cells)
{
    int x = 1, y = 1;
    int px = 0, py = 0;
    int nx, ny;
    int count = 0;
    while (true)
    {
        count++;
        bool found = false;
        for (auto m : moves)
        {
            int x2 = x + m.first;
            int y2 = y + m.second;
            if (cells[x2][y2] != 1 || (x2 == px && y2 == py))
            {
                continue;
            }
            if (found)
            {
                quit(_wa, "Not a path");
            }
            nx = x2, ny = y2;
            found = true;
        }
        if (found == (x == H && y == W))
        {
            quit(_wa, "Not a path");
        }
        if (x == H && y == W)
        {
            break;
        }
        px = x, py = y, x = nx, y = ny;
    }
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (cells[i][j] == 1)
            {
                count--;
            }
        }
    }
    if (count < 0)
    {
        quit(_wa, "Cell with color 1 outside the path");
    }
}

static const char NOT_SHORTEST[] = "Not a shortest path";

static bool check_shortest(const std::vector<std::vector<int>> &cells)
{
    std::vector<std::pair<int, int>> level = {{1, 1}};
    int px = 0, py = 1;
    std::vector<std::vector<bool>> visited(H + 2, std::vector<bool>(W + 2));
    visited[1][1] = true;
    bool cleanup = true;
    bool done = false;
    while (level.size())
    {
        bool has_path = false;
        std::vector<std::pair<int, int>> next_level;
        for (auto pos : level)
        {
            int x = pos.first, y = pos.second;
            if (cells[x][y] == 1)
            {
                if (has_path || done || abs(x - px) + abs(y - py) != 1)
                {
                    quit(_wa, NOT_SHORTEST);
                }
                px = x, py = y;
                has_path = true;
                if (x == H && y == W)
                {
                    done = true;
                }
            }
            else if (x == H && y == W)
            {
                quit(_wa, NOT_SHORTEST);
            }
            else if (cells[x][y] > 1)
            {
                cleanup = false;
            }
            for (auto m : moves)
            {
                int x2 = x + m.first;
                int y2 = y + m.second;
                if (cells[x2][y2] < 0 || visited[x2][y2])
                {
                    continue;
                }
                visited[x2][y2] = true;
                next_level.emplace_back(x2, y2);
            }
        }
        if (!done && !has_path)
        {
            quit(_wa, NOT_SHORTEST);
        }
        level = std::move(next_level);
    }
    return cleanup;
}

// The list of possible error messages sent by the grader
std::set<std::string> possible_errors = {
    "Invalid array",
    "Invalid color",
    "Invalid action",
    "Same state array",
};

[[noreturn]] void pv()
{
    quit(_pv, "Possible tampering with the output");
}

void communicate(const char *output_file)
{
    std::ifstream grader_output(output_file, std::ios::binary);
    if (!grader_output)
    {
        quit(_fail, "Cannot open file");
    };
    std::string grader_secret;
    std::getline(grader_output, grader_secret);
    if (grader_secret != output_secret)
    {
        pv();
    }
    std::string grader_result;
    std::getline(grader_output, grader_result);
    if (grader_result == "PV")
    {
        std::string grader_message;
        std::getline(grader_output, grader_message);
        if (!grader_output || !possible_errors.count(grader_message))
        {
            pv();
        }
        quit(_pv, grader_message);
    }
    else if (grader_result == "OK")
    {
        grader_output.read(reinterpret_cast<char *>(program), sizeof(program));
        grader_output.peek();
        if (!grader_output || !grader_output.eof())
        {
            pv();
        }
    }
    else
    {
        pv();
    }
}

void eval_testcase(const std::vector<std::vector<int>> &cells, bool &cleanup, int &max_steps)
{
    sim_state sim{cells};
    bool done = false;
    int steps = 0;
    while (!done && ++steps <= MAX_STEPS)
    {
        done = sim.step();
    }
    if (!done)
    {
        quit(_wa, "Too many steps");
    }
    check_path(sim.cells);
    cleanup &= check_shortest(sim.cells);
    max_steps = std::max(max_steps, steps);
}

template <class F>
std::vector<std::vector<int>> transform_testcase(const std::vector<std::vector<int>> &cells, F f)
{
    std::vector<std::vector<int>> transformed(H + 2, std::vector<int>(W + 2));
    for (int i = 0; i < H + 2; i++)
    {
        for (int j = 0; j < W + 2; j++)
        {
            std::pair<int, int> pos = f(i, j);
            transformed[i][j] = cells[pos.first][pos.second];
        }
    }
    return transformed;
}

double get_score(int colors, bool cleanup, bool partial)
{
    if (!partial)
    {
        return cleanup ? 1. : 0.5;
    }
    int res;
    if (colors >= 11)
    {
        res = 12 + (19 - colors) + 8 * cleanup;
    }
    else
    {
        int score[][2] = {
            {36, 46},
            {32, 42},
            {29, 38},
            {26, 34},
            {23, 31},
        };
        res = score[std::max(colors - 6, 0)][cleanup];
    }
    return res / 46.;
}

int main(int argc, char *argv[])
{
    // Keep alive on broken pipes
    struct sigaction sa;
    sa.sa_handler = SIG_IGN;
    sigaction(SIGPIPE, &sa, NULL);

    testlibMode = _checker;
    ouf.init(stdout, _output);
    if (argc < 3)
    {
        quit(_fail, "Insufficient number of args for manager of 'robot'");
    }
    if (!(std::cin >> H >> W))
    {
        quit(_fail, "Invalid test data");
    }
    std::vector<std::vector<int>> cells(H + 2, std::vector<int>(W + 2));
    for (int j = 0; j <= W + 1; j++)
    {
        cells[0][j] = cells[H + 1][j] = -2;
    }
    for (int i = 1; i <= H; i++)
    {
        cells[i][0] = cells[i][W + 1] = -2;
        for (int j = 1; j <= W; j++)
        {
            bool cell;
            if (!(std::cin >> cell))
            {
                quit(_fail, "Invalid test data");
            }
            cells[i][j] = cell ? -1 : 0;
        }
    }
    std::string extra;
    std::cin >> extra;

    communicate(argv[1]);
    int used_colors = 0;
    for (instruction instr : program)
    {
        validate_instr(instr);
        if (instr)
        {
            used_colors = std::max(used_colors, color(instr));
        }
    }

    auto rotate_180 = [](int i, int j)
    { return std::make_pair(H + 1 - i, W + 1 - j); };
    auto reflect_diag1 = [](int i, int j)
    { return std::make_pair(j, i); };
    auto reflect_diag2 = [](int i, int j)
    { return std::make_pair(H + 1 - j, H + 1 - i); };

    bool cleanup = true;
    int max_steps = 0;
    eval_testcase(cells, cleanup, max_steps);
    if (extra.find('t') != std::string::npos)
    {
        eval_testcase(transform_testcase(cells, rotate_180), cleanup, max_steps);
        if (H == W)
        {
            eval_testcase(transform_testcase(cells, reflect_diag1), cleanup, max_steps);
            eval_testcase(transform_testcase(cells, reflect_diag2), cleanup, max_steps);
        }
    }
    bool partial = extra.find('p') != std::string::npos;
    double score = get_score(used_colors, cleanup, partial);
    if (score == 1)
    {
        quit(_ok);
    }
    else
    {
        quitp(score);
    }
}
stub.cpp: #include "robot.h"
#include <cassert>
#include <cinttypes>
#include <string>
#include <fstream>

static const int MAX_COLOR = 19;
static const int MAX_STATE = 5153632; // = (MAX_COLOR + 3) ^ 5

static const std::string output_secret = "p71c1rw3EvfjFcMVWG0EOedGbWDX5uUp";
static std::ofstream output;

[[noreturn]] static void die(const char *message)
{
    output << output_secret << "\n";
    output << "PV\n";
    output << message << "\n";
    output.close();
    exit(0);
}

static int encode_state(const std::vector<int> &S)
{
    int state = 0;
    for (int s : S)
    {
        state = (MAX_COLOR + 3) * state + s + 2;
    }
    return state;
}

using instruction = std::uint8_t;

static instruction encode_instr(char color, char action)
{
    if (!action)
    {
        return 0;
    }
    int index = std::string("HWSENT").find_first_of(action) + 1;
    return (index << 5) | color;
}

static instruction program[MAX_STATE];

void set_instruction(std::vector<int> S, int Z, char A)
{
    if (S.size() != 5)
    {
        die("Invalid array");
    }
    for (int s : S)
    {
        if (s < -2 || s > MAX_COLOR)
        {
            die("Invalid array");
        }
    }
    if (Z < 0 || Z > MAX_COLOR)
    {
        die("Invalid color");
    }
    if (std::string("HWSENT").find_first_of(A) == std::string::npos)
    {
        die("Invalid action");
    }
    int code = encode_state(S);
    if (program[code])
    {
        die("Same state array");
    }
    program[code] = encode_instr(Z, A);
}

int main(int argc, char *argv[])
{
    assert(argc >= 3);
    output.open(argv[2], std::ios::binary);
    program_pulibot();
    output << output_secret << "\n";
    output << "OK\n";
    for (instruction instr : program)
    {
        output.put(instr);
    }
    return 0;
}


Setup script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Setup Script (Robot Problem) ---"

# --- Fixed Files (Problem Specific) ---
STUB_CPP="stub.cpp"          # Stub for the robot problem
MANAGER_CPP="manager.cpp"      # Manager for the robot problem
HEADER="robot.h"             # Header for the robot problem
TESTLIB_HEADER="testlib.h"     # Needed by the manager

# --- Argument Parsing ---
# Expect exactly one argument: solution_file
if [ "$#" -ne 1 ]; then
    echo "Usage: $0 <path/to/solution.cpp>" >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument

# --- File Checks (Compilation Prerequisites) ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for compilation..."
check_file "$SOLUTION_CPP"
check_file "$STUB_CPP"
check_file "$MANAGER_CPP"
check_file "$HEADER"
check_file "$TESTLIB_HEADER" # Check for testlib.h
check_tool "g++"
echo "Checks passed."
echo "Setup for Solution: $SOLUTION_CPP"

# --- Dynamic Naming (Executables) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
# Executable that compiles the user solution into program instructions
COMPILER_EXE="./${SOLUTION_BASENAME}_compiler_exe"
# Fixed manager executable name (must match setup.sh)
MANAGER_EXE="./robot_manager_exe"

# --- Compile Solution Compiler (if it doesn't exist) ---
if [ ! -f "$COMPILER_EXE" ]; then
    echo "Compiling solution ($SOLUTION_CPP + $STUB_CPP) into $COMPILER_EXE ..."
    g++ -std=c++17 "$SOLUTION_CPP" "$STUB_CPP" -o "$COMPILER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Solution compiler compilation failed." >&2
        exit 1
    fi
    echo "Solution compiler compiled successfully."
else
    echo "Using existing solution compiler executable: $COMPILER_EXE"
fi

# --- Compile Manager (if it doesn't exist) ---
if [ ! -f "$MANAGER_EXE" ]; then
    echo "Compiling manager ($MANAGER_CPP) into $MANAGER_EXE ..."
    g++ -std=c++17 "$MANAGER_CPP" -o "$MANAGER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Manager compilation failed." >&2
        # Optional: remove compiler exe if manager fails?
        # rm -f "$COMPILER_EXE"
        exit 1
    fi
    echo "Manager compiled successfully."
else
    echo "Using existing manager executable: $MANAGER_EXE"
fi

echo "Setup complete. Executables ready:"
echo "  Manager: $MANAGER_EXE"
echo "  Solution Compiler: $COMPILER_EXE"

exit 0


Evaluation script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Evaluation Script (Robot Problem) ---"

# --- Argument Parsing ---
# Expect exactly two arguments: solution_file and input_file
if [ "$#" -ne 2 ]; then
    echo "Usage: $0 <path/to/solution.cpp> <path/to/input.txt>" >&2
    echo "Note: Run setup_robot.sh <path/to/solution.cpp> first to compile." >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument
INPUT_TXT="$2"    # Get input file from second argument

# --- File & Tool Checks ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for evaluation..."
check_file "$INPUT_TXT"
check_tool "/usr/bin/time" # Check for the time command specifically
echo "Checks passed."
echo "Using Solution: $SOLUTION_CPP"
echo "Using Input:    $INPUT_TXT"

# --- Dynamic Naming (Consistent with setup_robot.sh) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
INPUT_BASENAME=$(basename "$INPUT_TXT" .in) # Assuming .in extension for inputs
# Executable names derived from solution basename (must match setup_robot.sh)
COMPILER_EXE="./${SOLUTION_BASENAME}_compiler_exe"
# Fixed manager executable name (must match setup_robot.sh)
MANAGER_EXE="./robot_manager_exe"
# Intermediate file with compiled instructions
PROGRAM_BIN="${INPUT_BASENAME}_${SOLUTION_BASENAME}_program.bin" # Make bin name specific to input+solution
# Final result file from the manager
RESULTS_TXT="${INPUT_BASENAME}_${SOLUTION_BASENAME}.results.txt"
# Temporary file for resource usage output
TIME_OUTPUT_FILE="${INPUT_BASENAME}_${SOLUTION_BASENAME}.time.txt"

# Check if executables exist (created by setup_robot.sh)
echo "Checking for compiled executables..."
check_file "$COMPILER_EXE"
check_file "$MANAGER_EXE"
echo "Executables found."

# Initialize exit codes
COMPILER_EXIT_CODE=-1
MANAGER_EXIT_CODE=-1

# --- Cleanup Function ---
# This function will be called on script exit (normal or error)
cleanup() {
    local script_exit_code=$?
    echo "Cleaning up evaluation run (Exit Code: $script_exit_code)..."
    # Remove intermediate files
    rm -f "$PROGRAM_BIN" "$TIME_OUTPUT_FILE"
    echo "Cleanup finished."
    # Exit with the original exit code that triggered the trap
    exit $script_exit_code
}
# Register the cleanup function to run on EXIT, INT, TERM signals
trap cleanup EXIT INT TERM

# --- Generate Program Instructions (if needed) ---
if [ ! -f "$PROGRAM_BIN" ]; then
    echo "Generating instructions file ($PROGRAM_BIN)..."
    # Run the compiler executable to generate the binary
    # Use '|| true' temporarily to prevent set -e exit if compiler fails
    "$COMPILER_EXE" "dummy_arg1" "$PROGRAM_BIN" || true
    COMPILER_EXIT_CODE=$? # Capture compiler's exit code
    if [ $COMPILER_EXIT_CODE -ne 0 ]; then
        echo "ERROR: Solution compiler failed during execution (Exit Code: $COMPILER_EXIT_CODE)." >&2
        # No need to proceed if binary generation failed
        exit $COMPILER_EXIT_CODE
    fi
    echo "Program binary generated successfully."
    COMPILER_EXIT_CODE=0 # Set to 0 if successful
else
    echo "Using existing program binary: $PROGRAM_BIN"
    COMPILER_EXIT_CODE=0 # Indicate success as we are using existing file
fi

# --- Evaluate ---
echo "Running manager with $PROGRAM_BIN and input $INPUT_TXT (measuring resources)..."
# Manager expects program file as argv[1]. Needs argc >= 3. Reads test case from stdin.
# Use /usr/bin/time to measure the manager process
# Use '|| true' temporarily to prevent set -e exit if manager fails
/usr/bin/time -f "Manager CPU Time (User+Sys): %U + %S seconds\nManager Max Memory: %M KB" \
              -o "$TIME_OUTPUT_FILE" \
              "$MANAGER_EXE" "$PROGRAM_BIN" "dummy_arg2" < "$INPUT_TXT" > "$RESULTS_TXT" || true
MANAGER_EXIT_CODE=$? # Capture manager's exit code

# --- Show Result ---
echo ""
echo "--- Evaluation Result ($RESULTS_TXT) ---"
# Check if results file exists and is readable before catting
if [ -r "$RESULTS_TXT" ]; then
    cat "$RESULTS_TXT"
else
    echo "ERROR: Result file '$RESULTS_TXT' not found or not readable." >&2
fi
echo "-----------------------------------------"

# --- Show Resource Usage ---
echo ""
echo "--- Resource Usage (Manager Process) ---"
if [ -r "$TIME_OUTPUT_FILE" ]; then
    cat "$TIME_OUTPUT_FILE"
else
     if [ $MANAGER_EXIT_CODE -ne 0 ]; then
         echo "Manager process did not complete normally; resource usage may be incomplete or unavailable." >&2
     else
         echo "ERROR: Time output file '$TIME_OUTPUT_FILE' not found or not readable." >&2
     fi
fi
echo "-----------------------------------------"

# --- Show Exit Codes ---
echo ""
echo "--- Process Exit Codes ---"
echo "Solution Compiler Exit Code: $COMPILER_EXIT_CODE" # Exit code from generating the binary
echo "Manager Exit Code:           $MANAGER_EXIT_CODE"
# Add warnings for non-zero exit codes
if [ $COMPILER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Solution compiler exited with non-zero status ($COMPILER_EXIT_CODE)" >&2
fi
if [ $MANAGER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Manager process exited with non-zero status ($MANAGER_EXIT_CODE)" >&2
fi
echo "--------------------------"

echo "--- Evaluation Complete ---"

# Exit the script with the manager's exit code
# The 'trap cleanup EXIT' will run before the script finally terminates
exit $MANAGER_EXIT_CODE