AT_abc170_f [ABC170F] Pond Skater

题目描述

水黾君住在一个南北方向有 $H$ 行、东西方向有 $W$ 列的矩形网格状池塘中。我们将从北往南第 $i$ 行、从西往东第 $j$ 列的格子记作格子 $(i,j)$。

有些格子上漂浮着荷叶，水黾君不能进入这些格子。若 $c_{ij}$ 为 @，表示格子 $(i,j)$ 上有荷叶；若为 .，则表示没有荷叶。

水黾君每次划水可以向东西南北任意一个方向移动不少于 $1$ 格、不多于 $K$ 格。在移动过程中，不能经过有荷叶的格子，也不能移动到有荷叶的格子或池塘外面。

请你求出水黾君从格子 $(x_1,y_1)$ 移动到 $(x_2,y_2)$ 至少需要划水多少次。如果无法到达，请指出这一点。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$ $K$ $x_1$ $y_1$ $x_2$ $y_2$
$c_{1,1}c_{1,2}\ldots c_{1,W}$
$c_{2,1}c_{2,2}\ldots c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}\ldots c_{H,W}$

输出格式

输出水黾君从格子 $(x_1,y_1)$ 到 $(x_2,y_2)$ 至少需要划水的次数。如果无法到达，则输出 -1。

输入输出样例 #1

输入 #1

3 5 2
3 2 3 4
.....
.@..@
..@..

输出 #1

5

输入输出样例 #2

输入 #2

1 6 4
1 1 1 6
......

输出 #2

2

输入输出样例 #3

输入 #3

3 3 1
2 1 2 3
.@.
.@.
.@.

输出 #3

-1

说明/提示

限制条件

• $1\leq H,W,K\leq 10^6$
• $H\times W\leq 10^6$
• $1\leq x_1,x_2\leq H$
• $1\leq y_1,y_2\leq W$
• $x_1\neq x_2$ 或 $y_1\neq y_2$
• $c_{i,j}$ 只为 . 或 @
• $c_{x_1,y_1} = .$
• $c_{x_2,y_2} = .$
• 所有输入均为整数。

样例解释 1

一开始，水黾君在格子 $(3,2)$。可以通过如下 $5$ 次划水到达格子 $(3,4)$：

• 从 $(3,2)$ 向西移动 $1$ 格，到达 $(3,1)$。
• 从 $(3,1)$ 向北移动 $2$ 格，到达 $(1,1)$。
• 从 $(1,1)$ 向东移动 $2$ 格，到达 $(1,3)$。
• 从 $(1,3)$ 向东移动 $1$ 格，到达 $(1,4)$。
• 从 $(1,4)$ 向南移动 $2$ 格，到达 $(3,4)$。

由 ChatGPT 4.1 翻译