有始有终

题号：NC219033
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个 ${N}$ 行 ${M}$ 列的矩阵，矩阵中每个元素都是 ${0 \sim 99}$ 的整数代表对应格的高度，若两格的高度之差不超过 ${D}$ ，则从一格可以移动到另一格。同时，可以使用一种技能，技能的效果是将该格变为电梯，这样该格和其相邻的格所有格都可以忽略高度差限制。现在给出起点和终点，计算从起点走到终点最少使用的技能数。

输入描述:

第一行一个数字 $T,(T \le 200)$ ，代表接下来测试数据的组数

对于每个测试数据，第一行有两个数字 ${M,N}$ ，表示著矩阵的大小，每行有 ${M}$ 个数字，共 ${N}$ 行 $(1 \le M,N \le 30)$ 。

第二行有两个数字 $Sx,Sy (1 \le Sx \le M, 1 \le Sy \le N)$ ，代表起点座标。

第三行有两个数字 $Px,Py (1 \le Px \le M, 1 \le Py \le N)$ ，代表终点座标。

第四行有一个数字 ${D}$ ，代表能往相邻且高度差不大于 ${D}$ 的矩阵格行走 $(0 \le D \le 100)$ 。

最后的 ${N}$ 行，每行有 ${M}$ 个用空白隔开的整数，为每个矩阵格的高度，且介于 ${0}$ 到 ${99}$ 之间(包含 ${0}$ 和 ${99}$ )。

请注意，地图的左上角座标为 ${(1, 1)}$ ，而右下角为 ${ (M,N)}$ 。

输出描述:

对于每组测试数据，输出一个非负整数代表使用技能的次数

示例1

输入

复制

2
9 9
1 1
5 5
3
9 9 9 9 9 9 9 9 9
1 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 1 9
9 1 1 1 1 1 9 1 9
9 1 9 9 9 1 9 1 9
9 1 9 1 1 1 9 1 9
9 1 9 9 9 9 9 1 9
9 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 9 9
21 14
17 12
14 11
0
7 85 12 80 90 45 78 13 57 39 61 81 32 62 49 32 45 72 65 41 39
33 37 53 31 4 24 95 53 66 32 70 30 76 49 65 68 83 15 83 47 19
83 0 67 74 15 62 42 79 85 15 51 65 53 14 90 62 37 7 42 22 7
45 1 62 5 38 84 73 0 73 50 84 41 12 13 33 79 87 86 38 59 61
72 38 24 11 72 1 56 1 11 8 50 34 57 52 80 71 17 23 72 88 77
82 9 93 70 73 57 18 27 52 60 26 47 23 56 21 16 85 87 85 63 64
12 45 77 84 25 43 35 69 17 40 69 86 57 29 55 43 53 88 0 33 64
15 78 28 91 52 91 66 42 10 47 39 60 23 5 7 42 59 82 91 33 0
68 6 35 81 7 80 42 16 78 53 79 3 15 94 74 15 48 16 91 8 65
35 41 8 74 54 41 94 71 65 65 8 81 12 13 68 94 30 1 3 12 88
80 31 58 3 45 15 23 71 80 89 95 93 28 39 3 72 63 61 41 63 57
73 52 14 32 92 5 30 2 56 34 18 77 75 22 84 76 91 24 47 83 66
17 30 61 93 88 4 51 95 1 94 48 75 86 86 67 1 3 89 85 88 56
11 12 14 11 57 14 92 60 16 74 14 61 45 52 81 82 52 79 45 53 4

2
9 9
1 1
5 5
3
9 9 9 9 9 9 9 9 9
1 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 1 9
9 1 1 1 1 1 9 1 9
9 1 9 9 9 1 9 1 9
9 1 9 1 1 1 9 1 9
9 1 9 9 9 9 9 1 9
9 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 9 9
21 14
17 12
14 11
0
7 85 12 80 90 45 78 13 57 39 61 81 32 62 49 32 45 72 65 41 39
33 37 53 31 4 24 95 53 66 32 70 30 76 49 65 68 83 15 83 47 19
83 0 67 74 15 62 42 79 85 15 51 65 53 14 90 62 37 7 42 22 7
45 1 62 5 38 84 73 0 73 50 84 41 12 13 33 79 87 86 38 59 61
72 38 24 11 72 1 56 1 11 8 50 34 57 52 80 71 17 23 72 88 77
82 9 93 70 73 57 18 27 52 60 26 47 23 56 21 16 85 87 85 63 64
12 45 77 84 25 43 35 69 17 40 69 86 57 29 55 43 53 88 0 33 64
15 78 28 91 52 91 66 42 10 47 39 60 23 5 7 42 59 82 91 33 0
68 6 35 81 7 80 42 16 78 53 79 3 15 94 74 15 48 16 91 8 65
35 41 8 74 54 41 94 71 65 65 8 81 12 13 68 94 30 1 3 12 88
80 31 58 3 45 15 23 71 80 89 95 93 28 39 3 72 63 61 41 63 57
73 52 14 32 92 5 30 2 56 34 18 77 75 22 84 76 91 24 47 83 66
17 30 61 93 88 4 51 95 1 94 48 75 86 86 67 1 3 89 85 88 56
11 12 14 11 57 14 92 60 16 74 14 61 45 52 81 82 52 79 45 53 4

输出

复制

0
2