Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.

Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.

Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

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.

Input

Input is given from Standard Input in the following format:

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

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

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

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

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

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

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

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
L = []
R = []
for i in range(Q):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)
    
import numpy as np
A = np.array(A)
for i in range(Q):
    MP = 0
    point = L[i]
    for j in range(int((R[i] - L[i]) / D)):
        start = np.array(np.where(A == point)).T.reshape(2)
        end = np.array(np.where(A == (point+D))).T.reshape(2)
        MP += sum(abs(start - end))
        point += D
    print(MP)

Submission status: Time Limit Exceeded

Solution code:
from  functools import lru_cache

@lru_cache(maxsize = 2**17)
def get_coord(num, H, W, masu):
    for i in range(H):
        for j in range(W):
            if masu[i][j] == num:
                return i, j

H, W, D = map(int, input().split())
masu = [[] for i in range(H)]
for i in range(H):
    masu[i] = tuple([int(i) for i in input().split()])
masu = tuple(masu)
Q = int(input())

exam = [[] for i in range(Q)]
for i in range(Q):
    exam[i] = [int(i) for i in input().split()]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = get_coord(num, H, W, masu)
    while num < exam[i][1]:
        coord2 = get_coord(num + D, H, W, masu)
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        num += D
        coord1 = coord2
    print(reduce_MP)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())

board=[0 for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        board[i*w+j]=int(a)

q=int(input())


distances=[-1 for _ in range(h*w)]

for _ in range(q):
    l,r=map(int,input().split())


    res=0
    while(l!=r):
        if distances[l]==-1:
            tmp=board.index(l)
            i=tmp//w
            j=tmp%w
            tmp=board.index(l+d)
            x=tmp//w
            y=tmp%w
            distances[l]=abs(i-x)+abs(j-y)
        res+=distances[l]
        l+=d
    print(res)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return 0, 0

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = check_val(H, W, A, next)
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    h, w, d = map(int, input().split())

    a = [(0,0) for i in range(h*w+1)]
    for y in range(h):
        row = list(map(int, input().split()))
        for x, v in enumerate(row):
            a[v] = (x, y)

    q = int(input())

    l, r = [], []

    for i in range(q):
        l_, r_ = map(int, input().split())
        l.append(l_)
        r.append(r_)

    # print(h, w, d)
    # print(a)
    # print(l, r)

    from collections import defaultdict
    memo = defaultdict(int)

    # qi 回目の試験を計算
    for qi in range(q):
        sum_magic = 0
        l_, r_ = l[qi], r[qi]
        #print(l_, r_)
        # mi 回目の移動の魔力
        for mi in range((r_-l_)//d):
            fr = l_ + d * (mi)
            to = l_ + d * (mi+1)

            # 履歴があれば使う
            ans_histo = memo[(fr, to)]
            if ans_histo > 0:
                sum_magic += ans_histo
                # print(fr, to, ans_histo, sum_magic, memo)
                continue

            # なければ計算
            frx, fry = a[fr]
            tox, toy = a[to]
            dist = abs(frx-tox) + abs(fry-toy)
            # print(mi, fr, to, dist)

            # メモ
            memo[(fr, to)] = dist
            sum_magic += dist

        print(sum_magic)

solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(numbers, queries, H, W, D):
    dp = [[-1] * (H*W+1) for _ in range(H*W+1)]

    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            if dp[l][r] == -1:
                dp[l][r] = sub_solve(l, l+D)
            res = dp[l][r]
            ans += res
            l += D
        print(ans)

numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i][i+D]
  distances[i%D]+=[d]
distances2 = [[0] for i in range(D)]#累積和に直す
for i in range(D):
  K = len(distances[i])
  for j in range(K):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(distances2[q][r]-distances2[q][l])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    coordinates = np.zeros([H*W+1, 2], dtype=int)
    for i in range(H):
        line = list(map(int, input().split()))
        for j, x in enumerate(line):
            coordinates[x] = i, j


    # board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    # coordinates = np.array([np.where(board == i+1) for i in range(H*W)]).reshape(H*W, 2)
    # coordinates = np.array([np.array(np.where(board == i+1)).reshape(-1) for i in range(H*W)])
    x_coordinates, y_coordinates = np.split(coordinates, 2, axis=1)
    # print(coordinates)

    memo = {}

    for L, R in Qs:
        if L == R:
            print(0)
            continue
        elif (L, R) in memo:
            print(memo[(L, R)])
            continue
        nums = np.arange(L, R+D, D)
        xs = x_coordinates[nums]
        ys = y_coordinates[nums]
        # print(nums, xs, ys)

        ans = np.sum(np.abs(xs[1:] - xs[:-1])) + np.sum(np.abs(ys[1:] - ys[:-1]))
        print(ans)

        memo[(L, R)] = ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy as sp
from collections import Counter

H, W, D = [int(a) for a in input().split()]

a = np.zeros([H*W+1, 2])
for i in range(H):
    a_ = [int(a) for a in input().split()]
    for j in range(W):
        a[a_[j]][0] = i
        a[a_[j]][1] = j

Q = int(input())
for _ in range(Q):
    l, r = [int(a) for a in input().split()]
    c = l
    p = 0
    while c < r:
        c_ = c + D
        p += abs(a[c][0] - a[c_][0]) + abs(a[c][1] - a[c_][1])
        c = c_
    print(int(p))

Submission status: Time Limit Exceeded

Solution code:
# Your code here!
h,w,d = map(int,input().split())

dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
for i in range(q):
    ans = 0
    l,r = map(int,input().split())
    current = l
    current_m = dic[l]
    while current < r:
        current += d
        next_m = dic[current]
        ans += abs(next_m[0]-current_m[0])+abs(next_m[1]-current_m[1])
        current_m = next_m
        
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

H, W, D = map(int, input().split())

num_dict = {}

for i in range(1, H + 1):
    line_num = map(int, input().split())
    for j, num in enumerate(line_num):
        num_dict[num] = [i, j + 1]

Q = int(input())

result_dict = {}
question_list = []

for k in range(Q):
    question_list += [input()]

question_set = set(question_list)

for question in question_set:
    L, R = map(int, question.split())
    result = 0
    while L != R:
        next_L = L + D

        p = num_dict[L]
        n = num_dict[next_L]

        result += abs(p[0] - n[0]) + abs(p[1] - n[1])
        L = next_L

    result_dict[question] = result

for question in question_list:
    print(result_dict[question])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for i in range(Q):
    tot = 0
    start = [(y, x) for x in range(W) for y in range(H) if A[y][x] == L[i]][0]
    while A[start[0]][start[1]] < R[i]:
        queue = [start]
        visited = set(queue)
        distances = [list(x) for x in [[0] * W] * H] 
        while len(queue) > 0:
            y, x = queue.pop(0)
            for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                y2, x2 = y + dy, x + dx
                if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
                    continue
                if (y2, x2) in visited:
                    continue
                visited.add((y2, x2))
                queue.append((y2, x2))
                distances[y2][x2] = distances[y][x] + 1
                if A[y2][x2] == A[start[0]][start[1]] + D:
                    queue = []
                    break
        tot += distances[y2][x2]
        start = (y2, x2)
    print(tot)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split(" "))
board = [input().split(" ") for i in range(h)]

q = int(input())
for i in range(q):
    l,r = map(int,input().split(" "))
    n = int((r-l)/d)
    count = 0
    x = []
    y = []
    for k in range(h):
        if str(l) in board[k]:
            x.append(board[k].index(str(l)))
            y.append(k)
        for j in range(n):
            if str(l+(j+1)*d) in board[k]:
                x.append(board[k].index(str(l+(j+1)*d)))
                y.append(k)
    for j in range(n):
        count = count + abs(int(x[j+1])-int(x[j])) + abs(y[j+1]-y[j])
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy
H, W, D = map(int, input().split())
A = numpy.array([list(map(int, input().split())) for i in range(H)])
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]


for l, r in LR:
    ans = 0
    z = l
    while z != r:
        zahyo1 = numpy.where(A==z)
        x1, y1 = int(zahyo1[0]), int(zahyo1[1])
        zahyo2 = numpy.where(A==z+D)
        x2, y2 = int(zahyo2[0]), int(zahyo2[1])
        ans += (abs(x1-x2)+abs(y1-y2))
        z = z + D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return sum(time[st-1+d: en: d])


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i][i+D]
  distances[i%D]+=[d]
distances2 = [[0] for i in range(D)]#累積和に直す
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(distances2[q][r]-distances2[q][l])

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())

locations=[(0,0)]*(H*W)
for i in range(H):
    row=list(map(int,input().split()))
    for j in range(W):
        locations[row[j]-1]=(i,j)
    

Q=int(input())

L=[]
R=[]
for i in range(Q):
    l,r=map(int,input().split())
    power=0
    x=l
    while x!=r:
        mFrom=locations[x-1]
        mTo=locations[x+D-1]
        power+=abs(mFrom[0]-mTo[0])+abs(mFrom[1]-mTo[1])
        x+=D
    print(power)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
index = [(0,0) for x in range(h*w+1)]
for i in range(1,h+1):
    col = list(map(int, input().split()))
    for j in range(1,w+1):
        index[col[j-1]] = (i, j)

q = int(input())
for i in range(q):
    ans = 0
    l, r = map(int, input().split())
    while l != r:
        ans += abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])
        l += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
xy = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(len(a)):
        xy[a[j]] = [j + 1, i + 1]
for i in range(int(input())):
    ans = 0
    l, r = map(int, input().split())
    for j in range(l, r, d):
        ans += abs(xy[j+d][0] - xy[j][0]) + abs(xy[j+d][1] - xy[j][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = list(map(int, input().split()))
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

def MP1step(s, t):
	for  i in range(H):
		for j in range(W):
			if A[i][j] == s:
				s_x = i
				s_y = j
	for  i in range(H):
		for j in range(W):
			if A[i][j] == t:
				t_x = i
				t_y = j
	return abs(t_x - s_x) + abs(t_y - s_y)

def MP1test(s, t):
	k = 0
	for i in range((t - s)//D):
		k += MP1step(s + D * i, s + D * (i + 1))
	return k

for i in range(Q):
	print(MP1test(LR[i][0], LR[i][1]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0


def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return sum(time[st-1+d: en: d])

for pr, ne in way:
    print(ask(pr, ne))

Submission status: Time Limit Exceeded

Solution code:
import sys,collections;sys.setrecursionlimit(10**7)
import itertools
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
Q = I()
for q in range(Q):
    l,r = Is()
    maho = 0
    for k in range(l,r,D):
        maho += abs(d[k+D][0] - d[k][0]) + abs(d[k+D][1] - d[k][1])
    print(maho)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())

locations=[(0,0)]*(H*W)
for i in range(H):
    row=list(map(int,input().split()))
    for j in range(W):
        locations[row[j]-1]=(i,j)
    

Q=int(input())

L=[]
R=[]
for i in range(Q):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)

for i in range(Q):
    power=0

    x=L[i]
    while x!=R[i]:
        mFrom=locations[x-1]
        mTo=locations[x+D-1]
        power+=abs(mFrom[0]-mTo[0])+abs(mFrom[1]-mTo[1])
        x+=D
    print(power)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    num = 0
    while L != R:
        num += abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        L += D
    print(num)

Submission status: Time Limit Exceeded

Solution code:

def get_coord(num, H, W, masu):
    for i in range(H):
        for j in range(W):
            if masu[i][j] == num:
                return i, j

H, W, D = map(int, input().split())
masu = []
for i in range(H):
    masu.append([int(i) for i in input().split()])
Q = int(input())

exam = []
for i in range(Q):
    exam.append([int(i) for i in input().split()])

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = get_coord(num, H, W, masu)
    while num < exam[i][1]:
        coord2 = get_coord(num + D, H, W, masu)
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        num += D
        coord1 = coord2
    print(reduce_MP)

Submission status: Time Limit Exceeded

Solution code:
def dist(a, b):
  return abs(a[0] - b[0]) + abs(a[1]- b[1])

H, W, D = map(int, input().split())
matrix = []
dic = {}
for h in range(H):
  line = list(map(int, input().split()))
  matrix.append(line)
  for idx,w in enumerate(line):
    dic[w] = (idx,h)

_ab_cost = {}
def ab_cost(L, R):
  if (L, R) in _ab_cost.keys():
    return _ab_cost[(L,R)]
  _cost = 0
  while L != R:
    _cost += dist(dic[L], dic[L+D])
    _ab_cost[(L, L+D)] = _cost
    L = L+D
  _ab_cost[(L,R)] = _cost
  return _ab_cost[(L,R)]

Q = int(input())
for q in range(Q):
  L, R = map(int, input().split())
  cost = 0
  if L == R:
    print(cost)
    continue
  cost = ab_cost(L, R)
  print(cost)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
As = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LRs = [list(map(int, input().split())) for i in range(Q)]

poss = [(0, 0)] * (H * W)
for i in range(H):
    for j in range(W):
        poss[As[i][j] - 1] = (i, j)

for L, R in LRs:
    ans = 0
    pi, pj = poss[L - 1]
    for i, j in poss[L - 1 + D:R + 1:D]:
        ans += abs(i - pi) + abs(j - pj)
        pi, pj = i, j
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())

for i in range(Q):
	mp=0
	L,R=list(map(int,input().split()))
	now=L
	while now!=R:
		mp+=abs(X[now+D][0]-X[now][0])+abs(X[now+D][1]-X[now][1])
		now+=D
	print(mp)

Submission status: Time Limit Exceeded

Solution code:
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
for i in range(q):
    power = 0
    pre_number = lr[i][0]
    next_number = lr[i][0] + hwd[2]
    while pre_number != lr[i][1]:
        power = power + abs(xy[pre_number - 1][0] - xy[next_number - 1][0]) + abs(xy[pre_number - 1][1] - xy[next_number - 1][1])
        pre_number = next_number
        next_number = next_number + hwd[2]
    print(power)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]

#dict = {a[i][j]: (i, j) for i in range(h) for j in range(w)}

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    
    ans = 0
    while l != r:
        y, x = dic[l - 1]
        ny, nx = dic[l + d - 1]
        
        ans += abs(ny - y) + abs(nx - x)
        l += d
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1


Q=input()
for i in range(Q):
	L,R=map(int,raw_input().split())
	ans=0
	for j in range(L,R,D):
		ans+=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
	print ans

Submission status: Time Limit Exceeded

Solution code:
def resolve(first, last, d, table):
    cost = 0
    val = first
    i, j = table[val]

    while val != last:
        x, y = table[val + d]
        cost += abs(x - i) + abs(y - j)
        i, j = x, y
        val += d

    return cost

def main():
    h, w, d = map(int, raw_input().split())
    table = [None for _ in xrange(h * w + 1)]

    for i in xrange(h):
        row = map(int, raw_input().split())
        for j in xrange(w):
            table[row[j]] = (i, j)

    q = int(raw_input())

    for _ in xrange(q):
        first, last = map(int, raw_input().split())
        print resolve(first, last, d, table)

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!A=int(input())

H,W,D=[int(i) for i in input().split()]
#AA=[]
KAZU=[0]*(H*W+1)
#print(KAZU)
for i in range(H):
#    AA=[int(i) for i in input().split()]
#    A.append(AA)
#    AA=[int(i) for i in input().split()]
    for (j, a) in enumerate(input().split()):
#        print(j,a)
        KAZU[int(a)] = [i,j] 

def cost(x, y):
    return abs(KAZU[x][0] -KAZU[y][0]) + abs(KAZU[x][1] -KAZU[y][1])

#print(KAZU)
Q=int(input())
for i in range(Q):
    C = 0
    l,r=[int(i) for i in input().split()]
    while l != r:
        C += cost(l,l+D)
        l += D
    print(C)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split(' '))

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split(' '))
    cnt = 0
    tmp = []
    if l != r:
        for k in range(int((r - l) / d) + 1):
            tmp.append(comp[l + d * k])
        for i in range(len(tmp)):
            if i >= 1:
                cnt += abs(tmp[i][0] - tmp[i - 1][0]) + abs(tmp[i][1] - tmp[i - 1][1])

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    # for L, R in Qs:
    #     power = 0
    #     while L != R:
    #         i, j = np.where(board == L)
    #         L += D
    #         x, y = np.where(board == L)
    #         power += int(abs(x-i) + abs(y-j))
    #     print(power)

    coordinates = np.array([np.array(np.where(board == i+1)).reshape(-1) for i in range(H*W)])
    x_coordinates, y_coordinates = np.split(coordinates, 2, axis=1)
    # print(coordinates)

    memo = {}

    for L, R in Qs:
        if L == R:
            print(0)
            continue
        elif (L, R) in memo:
            print(memo[(L, R)])
        nums = np.arange(L, R+D, D)-1
        xs = x_coordinates[nums]
        ys = y_coordinates[nums]
        # print(nums, xs, ys)

        ans = np.sum(np.abs(xs[1:] - xs[:-1])) + np.sum(np.abs(ys[1:] - ys[:-1]))
        print(ans)

        memo[(L, R)] = ans

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(h)]
q = int(input())
dic = {}


for i in range(h):
    for j in range(w):
        dic[A[i][j]] = (i+1,j+1)

for i in range(q):
    ans = 0
    l,r = map(int,input().split())
    current = l
    current_m = dic[l]
    while current != r:
        current += d
        next_m = dic[current]
        ans += abs(next_m[0]-current_m[0])+abs(next_m[1]-current_m[1])
        current_m = dic[current]
        
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().split())
    A = [
        list(map(int, input().split()))
        for _ in range(H)
    ]
    Q = int(input())
    LR = [
        list(map(int, input().split()))
        for _ in range(Q)
    ]

    f(H, W, D, A, Q, LR)


def f(H, W, D, A, Q, LR):
    pos = [None for _ in range(H * W + 1)]
    for y in range(H):
        for x in range(W):
            a = A[y][x]
            pos[a] = (x, y)

    for l, r in LR:
        ans = 0
        current = l
        target = r
        while current != target:
            _next = current + D
            i, j = pos[current]
            x, y = pos[_next]

            dist = abs(x - i) + abs(y - j)
            ans += dist

            # print((j, i), "to", (y, x), "cur", current, "next", _next, dist)
            current = _next

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())

A=[]
for i in range(H):
    A.append(list(map(int,input().split())))
    
locations=[(0,0)]*(H*W)
for i in range(H):
    for j in range(W):
        locations[A[i][j]-1]=(i,j)

Q=int(input())

L=[]
R=[]
for i in range(Q):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)

for i in range(Q):
    power=0

    x=L[i]
    while x!=R[i]:
        mFrom=locations[x-1]
        mTo=locations[x+D-1]
        power+=abs(mFrom[0]-mTo[0])+abs(mFrom[1]-mTo[1])
        x+=D
    print(power)

Submission status: Time Limit Exceeded

Solution code:
s = input().split()

H = int(s[0])
W = int(s[1])
D = int(s[2])

d = {}

for i in range(1, H+1):
    s = input().split()
    for j in range(W):
        d[int(s[j])] = (i, j+1)

Q = int(input())

for i in range(Q):
    mp = 0
    lr = input().split()
    L = int(lr[0])
    R = int(lr[1])
    while L != R:
        buffer = d[L]
        L += D
        mp += abs(d[L][0]-buffer[0])+abs(d[L][1]-buffer[1])
    print(mp)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
L = []
R = []
for i in range(Q):
    temp = list(map(int, input().split()))
    L.append(temp[0])
    R.append(temp[1])


table = {}
for h in range(H):
    for w in range(W):
        table[A[h][w]] = [h, w]


result = []
for q in range(Q):
    flag = True
    for i in range(q):
        if L[i] == L[q] and R[i] == R[q]:
            cost = result[i]
            flag = False
            break
    if flag:
        pos = [table[i] for i in range(L[q], R[q] + 1, D)]
        cost = sum([sum([abs(pos[i][j] - pos[i + 1][j]) for j in range(2)]) for i in range(len(pos) - 1)])

    result.append(cost)
    print(cost)