题目内容

户外直播人员要从城市中的出发格前往目标格，途中不能失去网络连接。把城区画成 $h$ 行、$w$ 列的格点图，图中部分格子设有基站。每座基站能覆盖与自身曼哈顿距离至多为 $r$ 的位置。

主播每走一步，只能进入上、下、左、右紧邻的一格，并且沿途经过的位置都必须由至少一座基站覆盖。请找出所需步数的最小值；无法抵达时给出 $-1$。

两格 $(u_1,v_1)$、$(u_2,v_2)$ 的曼哈顿距离定义为 $|u_1-u_2|+|v_1-v_2|$。例如 $(0,1)$ 与 $(2,4)$ 的距离是 $2+3=5$。

输入描述

首行依次给出 $h,w,r$。

第二行是出发位置 $a,b$，第三行是目标位置 $c,d$。

随后有 $h$ 行，每行给出 $w$ 个整数，组成矩阵 $g$。数值为 $1$ 的位置建有基站，为 $0$ 时没有基站。

输出描述

输出达到目标的最少步数；若不能保持连接走到目标，则打印 $-1$。

范围为 $1\le h,w\le100$，$0\le r\le100$；行坐标属于 $[0,h-1]$，列坐标属于 $[0,w-1]$。基站所在格可以通行。起点和终点也必须处于覆盖之内；二者相同时，只有该格被覆盖才输出 $0$。允许没有基站。

样例1

输入

2 4 1
0 0
1 3
1 0 1 0
0 1 0 1

输出

4

说明

所有格子均有覆盖，沿上行向右再向下，走 $4$ 步即可。

样例2

输入

2 3 0
0 0
1 2
1 0 1
0 0 1

输出

-1

说明

半径为 $0$，只有基站格有覆盖，出发格无法迈出第一步。