Exercise 12 | RACSO

Exercise _‹12_›:

Grid exploration 2

Solve the following exercise by means of a reduction to SAT:

Given a grid made of walkable cells, walls, and teleports, find a path fulfilling the following constraints:
- The path must start at a certain cell $s$ .
- The path cannot include walls.
- The path must see every walkable cell. A cell is seen if the path goes through it or through one of its up to $8$ adjacent cells (including diagonals).
- The path must not contain more than $k$ cells.
- The path is formed by means of the following types of moves:
  - Move to an adjacent cell (not including diagonals).
  - Use a teleport. A teleport has a source cell and a target cell, both of which are walkable, and can be used to move from the source to the target. A cell with a teleport can also be walked over normally, without triggering the teleport.
  - Go back to the starting cell $s$ . In other words, from any walkable cell in the grid it is possible to go back to the start cell $s$ with just one move, as if there was a teleport leading from each walkable cell back to $s$ .
- Teleports cannot be taken more than once (but you can go back to the starting cell as many times as you want).
For instance, for the grid
```
    ·   #   a   #   #

    ·   ·   ·   ·   ·

    ·   #   ·   #   ·

    ·   ·   ·   ·   ·

    #   #   A   #   s
```
in which walkable cells have been indicated with . or a letter and walls with #, and there is a teleport from $(4,2)$ (indicated with A) to $(0,2)$ (indicated with a), the following path
1. ```
    ·   #   a   #   #

    ·   ·   ·   ·   ·

    ·   #   ·   #   ·

    ·   · ← · ← · ← ·
                    ↑
    #   #   A   #   s
```
2. ```
    ·   #   a   #   #

    ·   ·   ·   ·   ·

    o   #   o   #   o

    o   o → o   o   o
            ↓
    #   #   o   #   o
```
3. ```
    ·   #   a   #   #
            ↓
    ·   · ← ·   ·   ·

    o   #   o   #   o

    o   o   o   o   o

    #   #   o   #   o
```
4. ```
    o   #   o   #   #

    o   o → o → o   ·

    o   #   o   #   o

    o   o   o   o   o

    #   #   o   #   o
```
5. ```
    o   #   o   #   #

    o   o   o   o   o

    o   #   o   #   o

    o   o   o   o   o

    #   #   o   #   o
```
has $12$ cells, counting $s$ and both ends of the teleport taken (seen cells are indicated with o).

The input of the exercise and the output with the solution (when the input is solvable) are as follows:

```
grid: array of array of int
k: int
s: struct {
   r: int
   c: int
}
teleports: array of struct {
   source: struct {
      r: int
      c: int
   }
   target: struct {
      r: int
      c: int
   }
}
```
The input has the matrix grid, the maximum number $k$ of cells in the path (counting $s$ ), the initial cell $s$ , and the teleport pairs. The grid contains the locations of the walls: grid[i][j] has a $0$ to denote that cell $(i,j)$ is walkable, and a $1$ to denote that the cell has a wall. The starting cell $s$ is a struct with two fields: r indicates the row, and c indicates the column. For instance, in the previous example we would have s.r ${} = {}$ s.c ${} = 4$ . It is guaranteed that every walkable cell is reachable from the cell $s$ without using teleports. The array teleports contains one entry per teleport. A teleport is a struct with fields source and target, which in turn are structs encoding cell coordinates with the usual r and c fields. For instance, in the previous example we would have a teleport t from cell $($ t.source.r $,$ t.source.c $) = (4,2)$ to cell $($ t.target.r $,$ t.target.c $) = (0,2)$ . There cannot be two identical teleports, i.e., with the same source and target.
```
path: array of struct {
   r: int
   c: int
}
```
The output consists of an array of variable length, containing the sequence of cells that form the path. Each element in the path is a struct with a pair of numbers r and c, with the same meaning as in s. The $0$ ’th element of the array must be s.

Authors: Nil Mamano / Documentation:

Exercise ‹12›:

Exercise _‹12_›: