3937: 混水摸鱼(挖土机 CSP-J 模拟赛 ~ 第十一场)

内存限制：256 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：4 解决：1

题目描述

33DAI 来到了一个大水塘抓鱼。可以把大水塘看作是一个 n 行 m 列的二维字符数组。第 x 行第 y 列的字符是 a_{x,y}。如果字符是 . 则表示是在正常水域，如果字符是 @ 则表示有大石头不能通行。

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

输入

第一行三个整数，n,m,k。

第二行四个整数，x_1,y_1,x_2,y_2。

接下来 n 行每行 m 列，第 i 行第 j 列为 a_{i,j}。

输出

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

样例输入 复制 

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

样例输出 复制 

5

提示


数据规模与约定

对于 100\% 的数据，保证：

  • 1 \le n,m,k \le 10^6
  • 1\le n\times m\le 10^6
  • 1\le x_1,x_2\le n
  • 1\le y_1,y_2\le m
  • x_1\neq x_2 或者 y_1\neq y_2
  • a_{i,j} 为 . 或 @
  • 保证 a_{x1,y1} 和 a_{x2,y2} 都不是 @

子任务划分：

  • 子任务 1（10 分）：保证 n=1
  • 子任务 2（20 分）：保证 n,m\le 1000 且 k=1
  • 子任务 3（30 分）：保证 k=1
  • 子任务 4（40 分）：没有特殊限制

来源/分类

提交提交记录统计露一手!