Description

总统 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)$ 涂成白色。

由于使用印章会弄脏他的手，他希望最小化操作次数。给定格子的颜色信息、印章的大小以及起始格子和目标格子的位置，编写一个程序计算他必须执行的最小操作次数，以便存在一条仅由白色格子组成的从起始格子到目标格子的路径。

Input Format

从标准输入读取以下数据。

$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)$ 的颜色。如果字符是 .，则颜色为白色；如果字符是 #，则颜色为黑色。

Output Format

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

2 4 2
1 1
2 4
.###
###.

1

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

4

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

1

1 15 1
1 15
1 1
...............

0

Hint

【样例解释 #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$ 均为整数。

题面翻译由 ChatGPT-4o 提供。