P9351 [JOI 2023 Final] 迷宫 / Maze

总统 K 喜欢解迷宫。他找到了可以用来创建迷宫的格子。这些格子是一个有 $R$ 行和 $C$ 列的矩形网格。每个格子要么是白色，要么是黑色。位于从上到下第 $i$ 行（$1 \leqslant i \leqslant R$）和从左到右第 $j$ 列（$1 \leqslant j \leqslant C$）的格子称为格子 $(i, j)$。 总统 K 将在可以通过白色格子而不能通过黑色格子的条件下解迷宫。更具体地，他将按以下方式解迷宫。 1. 在白色格子中，他将选择格子 $(S_r, S_c)$ 作为迷宫的起始格子，以及格子 $(G_r, G_c)$ 作为迷宫的目标格子。 2. 可以从一个格子移动到相邻的白色格子，方向可以是四个方向之一（上、下、左或右）。通过重复这个过程，他将找到从起始格子到目标格子的路径。 总统 K 已经固定了起始格子和目标格子。然而，他注意到在某些格子的颜色情况下，可能不存在一条仅由白色格子组成的从起始格子到目标格子的路径。他有一个大小为 $N \times N$ 的印章。他将多次执行以下**操作**，以便存在一条仅由白色格子组成的从起始格子到目标格子的路径。 **操作。** 他选择一个 $N \times N$ 的正方形区域，并将该区域内的格子涂成白色。更具体地，他选择整数 $a, b$ 满足 $1 \leqslant a \leqslant R - N + 1$ 和 $1 \leqslant b \leqslant C - N + 1$，对于每对整数 $(i, j)$ 满足 $a \leqslant i \leqslant a + N - 1$ 和 $b \leqslant j \leqslant b + N - 1$，他将格子 $(i, j)$ 涂成白色。 由于使用印章会弄脏他的手，他希望最小化操作次数。给定格子的颜色信息、印章的大小以及起始格子和目标格子的位置，编写一个程序计算他必须执行的最小操作次数，以便存在一条仅由白色格子组成的从起始格子到目标格子的路径。

从标准输入读取以下数据。 > $R$ $C$ $N$ $S_r$ $S_c$ $G_r$ $G_c$ $A_1$ $A_2$ $.$ $.$ $.$ $A_R$ $A_i (1 \leqslant i \leqslant R)$ 是一个长度为 $C$ 的字符串，由 `.` 或 `#` 组成。$A_i$ 的第 $j$ 个字符（$1 \leqslant j \leqslant C$）表示格子 $(i, j)$ 的颜色。如果字符是 `.`，则颜色为白色；如果字符是 `#`，则颜色为黑色。

向标准输出写入一行。输出应包含总统 K 必须执行的最小操作次数，以便存在一条仅由白色格子组成的从起始格子到目标格子的路径。

#### 【样例解释 #1】 如果他选择 $(a, b) = (1, 2)$ 并执行一次操作，格子 $(1, 2), (1, 3), (2, 2), (2, 3)$ 变成白色。然后将存在一条仅由白色格子组成的从起始格子到目标格子的路径。例如，路径 $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4)$ 满足条件。 如果他不执行任何操作，则不存在一条仅由白色格子组成的从起始格子到目标格子的路径。因此，输出 $1$。 该样例满足子任务 $2, 3, 4, 5, 6, 7, 8$ 的限制。 #### 【样例解释 #2】 该样例满足所有子任务的限制。 #### 【样例解释 #3】 该样例满足子任务 $2, 3, 4, 5, 6, 7, 8$ 的限制。 #### 【样例解释 #4】 即使他不执行任何操作，也可能存在一条仅由白色格子组成的从起始格子到目标格子的路径。 该样例满足所有子任务的限制。 #### 【数据范围】 对于所有测试数据，满足 $1 \leqslant N \leqslant R \leqslant C$，$R \times C \leqslant 6 \times 10^6$，$1 \leqslant S_r \leqslant R$，$1 \leqslant S_c \leqslant C$，$1 \leqslant G_r \leqslant R$，$1 \leqslant G_c \leqslant C$，$(S_r, S_c) eq (G_r, G_c)$。 保证 $A_i (1 \leqslant i \leqslant R)$ 是一个长度为 $C$ 且只由 `.` 或 `#` 构成的字符串。保证格子 $(S_r, S_c)$ 和格子 $(G_r, G_c)$ 均为白色。 保证 $R, C, N, S_r, S_c, G_r, G_c$ 均为整数。 | 子任务编号 | 分值 | 限制 | | :-: | :-: | :-: | | $1$ | $8$ | $N = 1, R \times C \leqslant 1.5 \times 10^6$ | | $2$ | $19$ | $R \times C \leqslant 10^3$ | | $3$ | $16$ | 答案不超过 $10$，$R \times C \leqslant 1.5 \times 10^6$ | | $4$ | $19$ | $R \times C \leqslant 6 \times 10^4$ | | $5$ | $5$ | $R \times C \leqslant 1.5 \times 10^5$ | | $6$ | $19$ | $R \times C \leqslant 1.5 \times 10^6$ | | $7$ | $8$ | $R \times C \leqslant 3 \times 10^6$ | | $8$ | $6$ | 无 | 题面翻译由 ChatGPT-4o 提供。