Practical Skill Test

题目描述

我们有一个有 $H$ 行 $W$ 列的网格。位于第 $i$ 行第 $j$ 列的方格称为方格 $(i,j)$。 整数 $1$ 到 $H×W$ 被写在整个网格上，方格 $(i,j)$ 上写的整数记为 $A_{i,j}$。 你，作为一名魔法少女，可以通过消耗 $|x-i|+|y-j|$ 点魔力将放在方格 $(i,j)$ 的棋子瞬移到方格 $(x,y)$。 现在你需要进行 $Q$ 次关于你作为魔法少女能力的实战测试。 第 $i$ 次测试按如下方式进行：

最初，棋子被放在写有整数 $L_i$ 的方格上。

令 $x$ 为棋子所处方格上写的整数。只要 $x$ 不是 $R_i$，就反复将棋子移动到写有整数 $x+D$ 的方格上。测试在 $x=R_i$ 时结束。

这里保证 $R_i-L_i$ 是 $D$ 的倍数。

对于每次测试，求该次测试中消耗的魔力点数之和。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $D$ $A_{1,1}$ $A_{1,2}$ $...$ $A_{1,W}$ : $A_{H,1}$ $A_{H,2}$ $...$ $A_{H,W}$ $Q$ $L_1$ $R_1$ : $L_Q$ $R_Q$

输出格式

对于每次测试，输出该次测试中消耗的魔力点数之和。 输出应按测试进行的顺序。

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

5

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

0
0

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

0
5
0

提示

$1 \leq H,W \leq 300$ $1 \leq D \leq H×W$ $1 \leq A_{i,j} \leq H×W$ $A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))$ $1 \leq Q \leq 10^5$ $1 \leq L_i \leq R_i \leq H×W$ $(R_i-L_i)$ is a multiple of $D$.方格 $(1,2)$ 上写着 $4$。

方格 $(3,3)$ 上写着 $6$。

方格 $(3,1)$ 上写着 $8$。

因此，第一次测试中消耗的魔力点数之和为 $(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$.
注意可能存在棋子根本不移动的测试，也可能有多个相同的测试。

标签: AtCoder|abc089D

来源

AtCoder|abc089D