题目描述

译自 JOI 2023 Final T3「迷路 / Maze」

K 理事长十分喜欢走迷宫。他发现了一个可以制作迷宫的方格场地。这个场地由 $R$ 行 $C$ 列单元格构成。每个方格被涂成黑白两种颜色之一。从上数第 $i$ 行从左数第 $j$ 列的方格被称为格子 $(i,j)$。

K 理事长走迷宫时可以经过白色格子，但不能经过黑色格子。更确切地说，他会按如下方式走迷宫。

1. 在白色格子中，他会选择格子 $(S_r,S_c)$ 作为起点，并选择格子 $(G_r,G_c)$ 作为终点。
2. 可以从一个格子移向上下左右四个方向与这个格子相邻的白色格子中。重复上述操作，他会找到一条从起点到终点的路径。

K 理事长已经确定了起点和终点。然而，他注意到在某些情况，如果是这样的格子颜色的话，可能不存在一条从起点到终点且只经过白色格子的路径。他有一个 $N\times N$ 大小的印章。他会进行如下操作几次，使得存在一条从起点到终点且只经过白色格子的路径。

• 操作：他选择一个 $N\times N$ 大小的正方形区域，然后把这个区域内所有格子涂白。更确切地说，他选择整数 $a,b$，满足 $1\le a\le R-N+1$ 且 $1\le b\le C-N+1$，然后对于所有满足 $a\le i\le a+N-1$ 和 $b\le j\le b+N-1$ 的 $(i,j)$，他会将格子 $(i,j)$ 涂成白色。

因为如果他用印章的话手会变脏，他想最小化操作次数。给出格子颜色，印章大小和起点与终点的位置，写一个程序计算他最少要进行多少次操作，才能使得存在一条从起点到终点且只经过白色格子的路径。

输入格式

第一行三个整数 $R,C,N$。

第二行两个整数 $S_r,S_c$。

第三行两个整数 $G_r,G_c$。

接下来 $R$ 行，每行一个长度为 $C$ 的字符串 $A_i$。字符串中仅包含 . 和 #。$A_i$ 中的第 $j$ 个字符表示格子 $(i,j)$ 的颜色。如果这个字符是 .，则表示这个格子是白色的，如果是 #，则表示格子是黑色的。

输出格式

输出一行，表示使得存在一条从起点到终点且只经过白色格子的路径的最小操作次数。

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

数据范围与提示

对于全部数据，满足

• $1\le N\le R\le C$
• $R\times C\le 6\times 10^6$
• $1\le S_r,G_r\le R,1\le S_c,G_c\le C,(S_r,S_c)\neq (G_r,G_c)$
• $A_i\ (1\le i\le R)$ 是长度为 $C$ 且仅由 . 和 # 构成的字符串
• 格子 $(S_r,S_c)$ 和 $(G_r,G_c)$ 都是白色的

详细子任务附加限制及分值如下表所示。