#2256. 混水摸鱼

混水摸鱼

题目背景

乘其阴乱,利其弱而无主。随,以向晦入宴息。

题目描述

立之 来到了一个大水塘抓鱼。可以把大水塘看作是一个 nnmm 列的二维字符数组。第 xx 行第 yy 列的字符是 ax,ya_{x,y}。如果字符是 . 则表示是在正常水域,如果字符是 @ 则表示有大石头不能通行。

立之 初始在第 x1x_1y1y_1 列。 她要抓的鱼在第 x2x_2 行第 y2y_2 列。她每次移动可以往上下左右四个方向之一走 1k1\sim k 步(假设走了 xx 步,则必须保证包括起点和终点及路程中的所有点这 x+1x+1 个位置都不能是大石头)。请问她最少几次移动可以到达鱼的位置。如果无法走到,输出 1-1

输入格式

第一行三个整数,n,m,kn,m,k

第二行四个整数,x1,y1,x2,y2x_1,y_1,x_2,y_2

接下来 nn 行每行 mm 列,第 ii 行第 jj 列为 ai,ja_{i,j}

输出格式

输出一个整数,即 立之 最少几次移动可以到达鱼的位置。如果无法走到,输出 1-1

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

移动路线可以为:(3,3),(3,2),(1,2),(1,3),(1,5),(3,5)(3,3),(3,2),(1,2),(1,3),(1,5),(3,5),一共移动了 55 步。

7 7 4
1 1 7 7
.......
.......
.......
.......
.......
.......
.......
4

移动路线可以为:(1,1),(1,3),(1,7),(4,7),(7,7)(1,1),(1,3),(1,7),(4,7),(7,7),一共移动了 44 步。

7 7 4
1 1 7 7
.......
.......
.......
.....@.
....@.@
....@..
.....@.
-1

显然你可以造一个中间一个大石头,隔开左上右下的输出 -1 的极限数据来检查自己会不会超时

数据规模与约定

对于 100%100\% 的数据,保证:

  • 1n,m,k1061 \le n,m,k \le 10^6
  • 1n×m1061\le n\times m\le 10^6
  • 1x1,x2n1\le x_1,x_2\le n
  • 1y1,y2m1\le y_1,y_2\le m
  • x1x2x_1\neq x_2 或者 y1y2y_1\neq y_2
  • ai,ja_{i,j}.@
  • 保证 ax1,y1a_{x1,y1}ax2,y2a_{x2,y2} 都不是 @

子任务划分:

  • 子任务 1(10 分):保证 n=1n=1
  • 子任务 2(20 分):保证 n,m1000n,m\le 1000k=1k=1
  • 子任务 3(30 分):保证 k=1k=1
  • 子任务 4(40 分):没有特殊限制