← 返回题目列表

AtCoder · abc170_f

F. 池塘溜冰者

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

Snuke,一种水黾,生活在一个长方形的池塘里,这个池塘可以看作是一个网格,上面有 H 东西向行和 W 南北柱。让 (i,j) 是位于 i从北数第 行, j从西数第 3 列。

有些方格上有荷叶,无法进入。 广场 (i,j) 上面有荷叶,如果 c_{ij} is @,如果 c_{ij} is ..

只需一笔,Snuke 就可以在 1 和 K 方格(含)朝向四个方向之一:北、东、南和西。 移动不得经过有荷叶的方格。移动到这样的广场或离开池塘也是禁止的。

求 Snuke 从广场出发所需的最少划数 (x_1,y_1) to (x_2,y_2)。 如果旅行从 (x_1,y_1) to (x_2,y_2) 是不可能的,请指出这一事实。

约束

  • 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 or y_1 \neq y_2.
  • c_{i,j} is . or @.
  • c_{x_1,y_1} = .
  • c_{x_2,y_2} = .
  • 输入的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

输出

打印 Snuke 从广场出发所需的最少笔划数 (x_1,y_1) to (x_2,y_2),或打印 -1 如果旅行不可能。


示例输入 1

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

示例输出 1

5

最初,Snuke 位于广场 (3,2)。 他可以到达广场 (3, 4) 按如下方式划五笔:

  • 来自 (3, 2),向西走一格到 (3, 1).

  • 来自 (3, 1),向北走两个方块到达 (1, 1).

  • 来自 (1, 1),向东走两格即可到达 (1, 3).

  • 来自 (1, 3),向东走一格到 (1, 4).

  • 来自 (1, 4),向南走两个广场即可到达 (3, 4).


示例输入 2

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

示例输出 2

2

示例输入 3

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

示例输出 3

-1