2023-ho-t3_Maze — JOI JOI
Task type: batch | Time limit: 2 s | Memory limit: 2048 MB | Difficulty: 23
Algorithms: bfs, graph theory, dijkstra, implementation, shortest path, graph traversal

![](_page_0_Picture_0.jpeg)

# 3. Maze

President K loves solving mazes. He found cells from which he may create a maze. The cells are a rectangular grid with $R$ horizontal rows and $C$ vertical columns. Each cell is colored either white or black. The cell in the $i$-th row ($1 \le i \le R$) from the top and the $j$-th column ($1 \le j \le C$) from the left is called Cell($i$, $j$).

President K will solve the maze under the condition that he can pass the white cells, but he cannot pass the black cells. More precisely, he will solve the maze in the following way:

1.  Among the white cells, he will choose Cell($S_r$, $S_c$), which is the starting cell of the maze, and Cell($G_r$, $G_c$), which is the goal cell of the maze.
2.  It is possible to move from one cell to another white cell which is adjacent to the current cell in one of the four directions (top, bottom, left, or right). By repeating this, he will find a path from the starting cell to the goal cell.

President K already fixed the starting cell and the goal cell. However, he noticed that in some situations of the colors of the cells, there might not be a path from the starting cell to the goal cell consisting of white cells only. He has a stamp of size $N \times N$. He will perform the following operations several times so that there will be a path from the starting cell to the goal cell consisting of white cells only.

**Operation:** He chooses a square region of $N \times N$ cells and paints the cells in the region white. More precisely, he chooses integers $a$, $b$ satisfying $1 \le a \le R - N + 1$ and $1 \le b \le C - N + 1$, and for every pair ($i$, $j$) of integers satisfying $a \le i \le a + N - 1$ and $b \le j \le b + N - 1$, he paints Cell($i$, $j$) white.

Since his hands become dirty if he uses the stamp, he wants to minimize the number of operations. Given information of the colors of the cells, the size of the stamp, and the locations of the starting cell and the goal cell, write a program which calculates the minimum number of operations he has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

![](_page_1_Picture_0.jpeg)

## Input

Read the following data from the standard input:

```
R C N
Sr Sc
Gr Gc
A1
A2
:
AR
```

$A_i$ ($1 \le i \le R$) is a string of length $C$ consisting of '.' or '#'. The $j$-th character ($1 \le j \le C$) of $A_i$ represents the color of Cell($i$, $j$). Its color is white if the character is '.', and its color is black if the character is '#'.

## Output

Write one line to the standard output. The output should contain the minimum number of operations President K has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

## Constraints

*   $1 \le N \le R \le C$.
*   $R \times C \le 6\,000\,000$.
*   $1 \le S_r \le R$.
*   $1 \le S_c \le C$.
*   $1 \le G_r \le R$.
*   $1 \le G_c \le C$.
*   $(S_r, S_c) \ne (G_r, G_c)$.
*   $A_i$ ($1 \le i \le R$) is a string of length $C$ consisting of '.' or '#'.
*   The color of Cell($S_r$, $S_c$) is white.
*   The color of Cell($G_r$, $G_c$) is white.
*   $R, C, N, S_r, S_c, G_r, G_c$ are integers.

![](_page_2_Picture_0.jpeg)

## Subtasks

1.  (8 points) $N = 1$, $R \times C \le 1\,500\,000$.
2.  (19 points) $R \times C \le 1\,000$.
3.  (16 points) The answer is less than or equal to 10, and $R \times C \le 1\,500\,000$.
4.  (19 points) $R \times C \le 60\,000$.
5.  (5 points) $R \times C \le 150\,000$.
6.  (19 points) $R \times C \le 1\,500\,000$.
7.  (8 points) $R \times C \le 3\,000\,000$.
8.  (6 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| `2 4 2`        | `1`            |
| `1 1`        |                |
| `2 4`        |                |
| `.#\##`       |                |
| `####.`       |                |

If he chooses ($a$, $b$) = (1, 2) and performs an operation, Cells (1, 2), (1, 3), (2, 2), (2, 3) become white. Then there will be a path from the starting cell to the goal cell consisting of white cells only. For example, the path (1, 1) $\rightarrow$ (1, 2) $\rightarrow$ (1, 3) $\rightarrow$ (2, 3) $\rightarrow$ (2, 4) satisfies the condition.

If he does not perform an operation, there is no path from the starting cell to the goal cell consisting of white cells only. Therefore, output 1.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

![](_page_3_Picture_0.jpeg)

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| `6 6 1`        | `4`             |
| `1 6`        |                 |
| `6 1`        |                 |
| `..#.#.`     |                 |
| `##.###`     |                 |
| `####.#`     |                 |
| `...###`     |                 |
| `##.##.`     |                 |
| `.#.###`     |                 |

This sample input satisfies the constraints of all the subtasks.

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| `6 7 6`        | `1`             |
| `6 4`        |                 |
| `3 1`        |                 |
| `..#.#.#`     |                 |
| `##.##..`     |                 |
| `.######`     |                 |
| `#..#.#.`     |                 |
| `.######`     |                 |
| `..#.##.`     |                 |

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

| Sample Input 4 | Sample Output 4 |
| :------------- | :------------- |
| `1 15 1`       | `0`             |
| `1 15`       |                 |
| `1 1`        |                 |
| `...............` |                 |

Even if he does not perform an operation, there might be a path from the starting cell to the goal cell consisting of white cells only.

This sample input satisfies the constraints of all the subtasks.

Starter code: