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:
def A_Sort(A,H,W):
    A_sorted = [None for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            A_sorted[A[i][j]-1] = (i,j)
    return A_sorted

def dist(x,y,A_sorted):
    si, sj = A_sorted[x-1]
    gi, gj = A_sorted[y-1]
    return abs(si-gi)+abs(sj-gj)



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)]

AA = A_Sort(A,H,W)

for i in range(Q):
    sum = 0
    for j in range((LR[i][1]-LR[i][0])//D):
        sum += dist(LR[i][0]+j*D,LR[i][0]+(j+1)*D, AA)
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for q in range(1,Q+1):
	l, r = L[q], R[q]
	C[l,l] = 0
	C[r,r] = 0
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		elif (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]

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)
 
inf = 10000000
d = [list(x) for x in [[inf] * (W * H + 1)] * (W * H + 1)]
for y in range(H):
    for x in range(W):
        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
            d[A[y][x]][A[y2][x2]] = 1
            d[A[y2][x2]][A[y][x]] = 1
 
for k in range(W * H + 1):
    for i in range(W * H + 1):
        for j in range(W * H + 1):
            if d[i][j] > d[i][k] + d[j][k]:
                d[i][j] = d[i][k] + d[j][k]
 
for i in range(Q):
    tot = 0
    curr = L[i]
    while curr < R[i]:
        start = [(y, x) for x in range(W) for y in range(H) if A[y][x] == curr][0]
        end = [(y, x) for x in range(W) for y in range(H) if A[y][x] == curr + D][0]
        tot += d[A[start[0]][start[1]]][A[end[0]][end[1]]]
        curr += D
    print(tot)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = [int(n) for n in raw_input().split(" ")]
A = [[None] * (W + 1)] * (H + 1)
Location = {}
for h in range(1,H + 1):
	A[h][1:W+1] = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A[h]):
		Location[a] = (h, w)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for l in L:
	C[l,l] = 0
for q in range(1,Q+1):
	l = L[q]
	r = R[q]
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		if (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]

Submission status: Time Limit Exceeded

Solution code:
H,W,D = [int(n) for n in raw_input().split(" ")]
A = [[None] * (W + 1)] * (H + 1)
Location = {}
for h in range(1,H + 1):
	A[h][1:W+1] = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A[h]):
		Location[a] = (h, w)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for l in L:
	C[l,l] = 0
for q in range(1,Q+1):
	l = L[q]
	r = R[q]
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [(-1, -1)] * 100000

for y in range(H):
    tmp = [int(x) for x in input().split()]
    for x, e in enumerate(tmp):
        A[e] = (x, y)

Q = int(input())
LR = [[int(e) for e in input().split()] for i in range(Q)]

for start, goal in LR:
    place = start
    point = 0

    while place != goal:
        placeX, placeY = A[place]
        nxtX, nxtY = A[place + D]

        point += (abs(nxtX - placeX) + abs(nxtY - placeY))
        place += D
    print(point)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [(-1, -1)] * 100000

for y in range(H):
    tmp = [int(x) for x in input().split()]
    for x in range(W):
        A[tmp[x]] = (x, y)

Q = int(input())
LR = [tuple([int(x) for x in input().split()]) for i in range(Q)]

for start, goal in LR:
    place = start
    nxt = place + D
    point = 0

    while place != goal:
        placeX, placeY = A[place]
        nxtX, nxtY = A[nxt]

        point += (abs(nxtX - placeX) + abs(nxtY - placeY))
        place += D
        nxt += D
    print(point)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in xrange(h)]
b = {a[x][y]: (x, y) for x in xrange(h) for y in xrange(w)}
for _ in xrange(input()):
    print sum([sum([abs(b[p][i] - b[p + d][i]) for i in [0, 1]])
               for p in xrange(*(map(int, raw_input().split()) + [d]))])

Submission status: Time Limit Exceeded

Solution code:
def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [telepo_test(LR[0], LR[1], D, board) for LR in LRs]

for r in result:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [get_coordinate(r, board) for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


def get_coordinate(n, board):
    for c, r in enumerate(board):
        if n not in r:
            continue
        return (c, r.index(n))
    else:
        return None


H, W, D = tuple(map(int, input().split()))
board = [tuple(map(int, input().split())) for _ in range(H)]
Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]

result = [telepo_test(LR[0], LR[1], D, board) for LR in LRs]
for r in result:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
HWD = input().split()
H = int(HWD[0])
W = int(HWD[1])
D = int(HWD[2])

num_array = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
	row = input().split()
	for j in range(W):
		num_array[i][j] = int(row[j])

q = int(input())
count_list = [0 for i in range(q)]

for k in range(q):
	LR = input().split()
	L = int(LR[0])
	R = int(LR[1])

	num_where = []
	for i in range(int((R - L)/D) + 1):
		current_num = L + D*i
		for i in range(H):
			for j in range(W):
				if num_array[i][j] == current_num:
					num_where.append([i, j])
					break
			else:
				continue
			break

	count = 0
	for i in range(int((R - L)/D)):
		count +=  abs(num_where[i][0] - num_where[i+1][0]) + abs(num_where[i][1] - num_where[i+1][1])
	count_list[k] = count

for i in range(q):
	print(count_list[i])

Submission status: Time Limit Exceeded

Solution code:
def telepo_test(start, goal, delta, board):
    c_s = get_coordinate(start, board)
    c_g = get_coordinate(goal, board)

    mp = 0
    while c_s != c_g:
        target = board[c_s[0]][c_s[1]] + delta
        c_t = get_coordinate(target, board)
        mp += abs(c_t[0] - c_s[0]) + abs(c_t[1] - c_s[1])
        c_s = c_t
    return mp


def get_coordinate(n, board):
    for c, r in enumerate(board):
        if n not in r:
            continue
        return (c, r.index(n))
    else:
        return None


H, W, D = tuple(map(int, input().split()))
board = [tuple(map(int, input().split())) for _ in range(H)]
Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [telepo_test(LR[0], LR[1], D, board) for LR in LRs]
for r in result:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().strip().split())
    MAP = {}
    for i in range(H):
        arr = map(int, input().strip().split())
        for j, x in enumerate(arr):
            MAP[x] = (i + 1, j + 1)
    Q = int(input().strip())
    CASE = []
    for k in range(Q):
        st, ed = map(int, input().strip().split())
        CASE.append((st, ed))

    DUP_CASE = {}
    for st, ed in CASE:
        count = 0
        if (st, ed) in DUP_CASE:
            count = DUP_CASE[(st, ed)]
        else:
            _st = st
            while _st != ed:
                cy, cx = MAP[_st]
                ny, nx = MAP[_st+D]
                count += abs(ny - cy) + abs(nx - cx)
                _st += D
            DUP_CASE[(st, ed)] = count
        print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().strip().split())
    MAP = {}
    for i in range(H):
        arr = map(int, input().strip().split())
        for j, x in enumerate(arr):
            MAP[x] = (i + 1, j + 1)
    Q = int(input().strip())
    CASE = []
    for k in range(Q):
        st, ed = map(int, input().strip().split())
        CASE.append((st, ed))

    for st, ed in CASE:
        count = 0
        while st != ed:
            cy, cx = MAP[st]            
            ny, nx = MAP[st+D]
            count += abs(ny - cy) + abs(nx - cx)
            st += D
        print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict ={}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)

Q = int(input())
result = {}
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        sum = 0
        Lj = int(tmp[0])
        Rj = int(tmp[1])
        count = int((Rj-Lj)/D)
        for k in range(count):
            posi1 = dict[str(Lj+D*k)].split()
            posi2 = dict[str(Lj+D*(k+1))].split()
            sum += abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        print(sum)
        result[tmpx] = sum

Submission status: Time Limit Exceeded

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict ={}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)

Q = int(input())

test = [[0 for x in range(2)] for y in range(Q)]
for j in range(Q):
    tmp = input().split()
    sum = 0
    Lj = int(tmp[0])
    Rj = int(tmp[1])
    count = int((Rj-Lj)/D)
    for k in range(count):
        posi1 = dict[str(Lj+D*k)].split()
        posi2 = dict[str(Lj+D*(k+1))].split()
        sum += abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
H,W,D =map(int,input().split())
x_amari=[[0 for i in range((H*W)//D if j>(H*W)%D else ((H*W)//D)+1 if j>0 else (H*W)//D )] for j in range(D)]
y_amari=[[0 for i in range((H*W)//D if j>(H*W)%D else ((H*W)//D)+1 if j>0 else (H*W)//D )] for j in range(D)]
for i in range(H):
    Hlist = list(map(int,input().split()))
    for j in range(W):
        x_amari[Hlist[j]%D][Hlist[j]//D if Hlist[j]%D!=0 else (Hlist[j]//D)-1]+=i+1
        y_amari[Hlist[j]%D][Hlist[j]//D if Hlist[j]%D!=0 else (Hlist[j]//D)-1]+=j+1
abslist=[[0 for i in range(len(x_amari[k])-1)] for k in range(D)]
for k in range(D):
    for i in range(len(x_amari[k])-1):
        abslist[k][i] += abs(x_amari[k][i+1]-x_amari[k][i])+abs(y_amari[k][i+1]-y_amari[k][i])
Q=int(input())
L=[]
R=[]
for _ in range(Q):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
for m in range(Q):
    amari= L[m]%D
    sho1=L[m]//D
    sho2=R[m]//D
    if sho1==sho2:
        print(0)
    elif amari==0:
        print(sum(abslist[0][sho1-1:sho2-1]))
    else:
        print(sum(abslist[amari][sho1:sho2]))

Submission status: Time Limit Exceeded

Solution code:
H,W,D =map(int,input().split())
x=[0 for _ in range(H*W)]
y=[0 for _ in range(H*W)]
for i in range(H):
    Hlist = list(map(int,input().split()))
    for j in range(W):
        x[Hlist[j]-1] +=i
        y[Hlist[j]-1] +=j
Q=int(input())
c=[0 for _ in range(Q)]
for k in range(Q):
    L,R=map(int,input().split())
    count=0
    for i in range((R-L)//D):
      count += abs(x[L+(i+1)*D-1]-x[L+i*D-1])+abs(y[L+(i+1)*D-1]-y[L+i*D-1])
    c[k] += count
for k in range(Q):
    print(c[k])

Submission status: Time Limit Exceeded

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


masu = [[0,0] for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        masu[A[i][j]-1] = [i, j]

MP = [0 for _ in range(Q)]
for k in range(Q):
    XY = masu[L[k]-1:R[k]:D]
    for i in range(len(XY)-1):
        MP[k] += abs(XY[i][0]-XY[i+1][0])
        MP[k] += abs(XY[i][1]-XY[i+1][1])


for i in range(Q):
    print(MP[i])

Submission status: Time Limit Exceeded

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


masu = [[0,0] for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        masu[A[i][j]-1] = [i, j]

MP = [0 for _ in range(Q)]
for k in range(Q):
    K = L[k]
    i, j = masu[K-1]
    while A[i][j] != R[k]:
        K = K + D
        x, y = masu[K-1]
        MP[k] += abs(x-i) + abs(y-j)
        i, j = x, y

for i in range(Q):
    print(MP[i])

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
	H, W, D = list(map(int, input().split()))
	masu_d = {}
	for i in range(H):
		inputs = list(map(int, input().split()))
		for j in range(W):
			masu_d[inputs[j]] = [i, j]

	Q = int(input())
	L = []
	R = []
	for i in range(Q):
		l, r = list(map(int, input().split()))
		L.append(l)
		R.append(r)
	# 総和計算開始
	for i in range(Q):
		ans = 0
		now_l = L[i]
		while 1:
			if now_l == R[i]:
				print(int(ans))
				break
			next_l = now_l + D
			ans += math.fabs(masu_d[now_l][0]-masu_d[next_l][0]) + math.fabs(masu_d[now_l][1]-masu_d[next_l][1])
			now_l = next_l

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
num = map(int,raw_input().split())
H = num[0]
W = num[1]
D = num[2]

lis = np.zeros((H * W,2))

for i in range(H):
    line = map(int,raw_input().split())
    l = 0
    for k in line:
        lis[k - 1][0] = i
        lis[k - 1][1] = l
        l += 1
        
times = int(raw_input())

k = 1

while k <= times:
    LR = map(int,raw_input().split())
    L = LR[0]
    R = LR[1]
    count = 0
    while L < R:
        count += abs(lis[L + D - 1][0] - lis[L - 1][0]) + abs(lis[L + D - 1][1] - lis[L - 1][1])
        L += D
    print int(count)
    k += 1

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
exam = [list(map(int, input().split())) for _ in range(Q)]

flat_a = list(chain.from_iterable(A))

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    tmp1 = flat_a.index(i+1)
    tmp2 = flat_a.index(i+D+1)
    S[i] = abs(tmp1%W - tmp2%W) + abs(tmp1//W - tmp2//W) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Submission status: Time Limit Exceeded

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

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    tmp1 = (0, 0)
    tmp2 = (0, 0)
    for j, Ai in enumerate(A):
        if i+1 in Ai:
            tmp1 = (Ai.index(i+1), j)
        if i+D+1 in Ai:
            tmp2 = (Ai.index(i+D+1), j)
    S[i] = abs(tmp1[0] - tmp2[0]) + abs(tmp1[1] - tmp2[1]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

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)]
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]


def INDEX(x):
    for i in range(H):
        if x in A[i]:
            for j in range(W):
                if x==A[i][j]:
                    return((i,j))
                
for q in LR:
    start=q[0]
    goal=q[1]
    distance=0
    while start!=goal:
        distance+=abs(INDEX(start)[0]-INDEX(start+D)[0])+abs(INDEX(start)[1]-INDEX(start+D)[1])
        start=start+D
    print(distance)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
 
condi = input()
H,W,D = condi.split()
H = int(H)
W = int(W)
D = int(D)
 
pref = np.zeros((H,W))
for i in range(H):
    row = input()
    row = row.split()
    for j in range(W):
            pref[i][j] = int(row[j])
mat = np.array(pref)
 
Q = input()
Q = int(Q)
for i in range(Q):
  MP = 0
  LR = input()
  L,R =LR.split()
  L = int(L)
  R = int(R)
  p,q = np.where(mat == L)
  while R>=L+D:
    x,y = np.where(mat == (L+D))
    MP = MP + math.fabs(x-p)+math.fabs(y-q)
    L = L + D
    p = x
    q = y
  print(int(MP))

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 -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    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 = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = dict_buf[str(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:
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 -1, -1

    check_list = []
    for i in range(Q):
        stat_LR = LR[i]
        for j in range(stat_LR[0], stat_LR[1]+D, D):
            check_list.append(j)
    check_list = list(set(check_list))

    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    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 = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = dict_buf[str(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 ACBC_089_D():
    _hwd = str(input()).split()
    _hwd = list(map(int, _hwd))
    _area = []
    _lrs = []

    for i in range(0, _hwd[0]):
        _aij = str(input()).split()
        _area.append(list(map(int, _aij)))

    _q = int(input())

    for i in range(0, _q):
        _lr = str(input()).split()
        _lrs.append(list(map(int, _lr)))

    for i in range(0, _q):
        _mpcount = 0
        for i2 in range(0, int((_lrs[i][1] - _lrs[i][0]) / _hwd[2]) + 1):
            for i3 in range(0, _hwd[0]):
                if _lrs[i][0] + _hwd[2] * i2 in _area[i3]:
                    if not i2:
                        _nowx = _area[i3].index(_lrs[i][0]) + 1
                        _nowy = i3 + 1
                    _nextx = _area[i3].index(_lrs[i][0] + _hwd[2] * i2) + 1
                    _nexty = i3 + 1
            _mpcount += abs(_nextx - _nowx) + abs(_nexty - _nowy)
            _nowx = _nextx
            _nowy = _nexty
        print(_mpcount)


ACBC_089_D()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, D = map(int, input().split())
pos = [None]*(H*W)

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

costs = [0]*(H*W)
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current - 1] = costs[current - 1 - D] + np.absolute(pos[current - 1][0] - pos[current - 1 - D][0]) + np.absolute(pos[current - 1][1] - pos[current - 1 - D][1])
        current += D

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    MP = costs[R-1] - costs[L-1]
    print(MP)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def one_game(i, D, A, start, end):
    current = np.array([])
    count = 0
    for X in range(start, end+1, D):
        old = np.copy(current)
        current = np.where(A==X)
        if X == start:
            continue
        count += abs(current[0][0] - old[0][0]) + abs(current[1][0] - old[1][0])
    return count

def f(H, W, D, A, Q, ST):
    A = np.array(A)
    counts = []
    for i in range(Q):
        start = ST[i][0]
        end = ST[i][1]
        count = one_game(i, D, A, start, end)
        counts.append(count)
    return counts

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

    counts = f(H, W, D, A, Q, ST)
    for i in range(Q):
        print(counts[i])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def count():
    pass

def one_game(i, D, A, start, end):
    current = np.array([])
    count = 0
    for X in range(start, end+1, D):
        old = np.copy(current)
        current = np.where(A==X)
        if X == start:
            continue
        count += abs(current[0][0] - old[0][0]) + abs(current[1][0] - old[1][0])
    return count

def f(H, W, D, A, Q, ST):
    A = np.array(A)
    counts = []
    for i in range(Q):
        start = ST[i][0]
        end = ST[i][1]
        count = one_game(i, D, A, start, end)
        counts.append(count)
    return counts

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

    counts = f(H, W, D, A, Q, ST)
    for i in range(Q):
        print(counts[i])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, D = map(int, input().split())
pos = [None]*(H*W)

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

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    if L == R:
        print(0)
    else:
        to_be_checked = [i for i in range(L, R+1, D)]
        moves = len(to_be_checked)
        pos_list = [pos[i-1] for i in to_be_checked]

        MP = sum([np.absolute(pos_list[i][0] - pos_list[i+1][0]) for i in range(moves-1)]) + sum([np.absolute(pos_list[i][1] - pos_list[i+1][1]) for i in range(moves-1)])

        print(MP)

Submission status: Time Limit Exceeded

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

q = int(input())

for i in range(q):
    res = 0
    count = 0
    start, end = (int(j) for j in input().split())
    for n in range(start, end+d, d):
        for x in range(w):
            for y in range(h):
                if arr[y][x] == n:
                    idx = [x, y]
                    break
        if count >= 1:
            res += abs(idx[0]-idx_tmp[0]) + abs(idx[1]-idx_tmp[1])
        idx_tmp = idx
        count += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.spatial.distance import cityblock

H,W,D = 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())))
A = np.array(A)

dist = {}

for q in range(Q):
    mp = 0
    l = LR[q][0]
    r = LR[q][1]
    while l != r:
        now = np.argwhere(A==l)
        next_spot = np.argwhere(A==(l+D))
        if l not in dist:
            dist[l] = cityblock(now,next_spot)
        mp += dist[l]
        l += D
    print(mp)

Submission status: Time Limit Exceeded

Solution code:

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

coord_dict_x = [0 for i in range(90002)]
coord_dict_y = [0 for i in range(90002)]

for i in range(H):
    gyo = [int(i) for i in input().split()]
    for j in range(W):
        coord_dict_x[gyo[j]] = i
        coord_dict_y[gyo[j]] = j

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

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1_x = coord_dict_x[num]
    coord1_y = coord_dict_y[num]
    while num < exam[i][1]:
        num += D
        coord2_x = coord_dict_x[num]
        coord2_y = coord_dict_y[num]
        reduce_MP += abs(coord1_x - coord2_x) + abs(coord1_y - coord2_y)
        coord1_x, coord1_y = coord2_x, coord2_y
    print(reduce_MP)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.spatial.distance import cityblock

H,W,D = 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())))
A = np.array(A)

for q in range(Q):
    mp = 0
    l = LR[q][0]
    r = LR[q][1]
    while (l < r):
        now = np.argwhere(A==l)
        next_spot = np.argwhere(A==(l+D))
        mp += cityblock(now,next_spot)
        l += D
    print(mp)

Submission status: Time Limit Exceeded

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

    grid = dict()
    for i, a in enumerate(A):
        for j, b in enumerate(a):
            grid[b] = (i, j)

    for l, r in LR:
        power = 0
        while 1:
            if l == r:
                break
            else:
                i, j = grid[l]
                x, y = grid[l+D]
                power += abs(x - i) + abs(y - j)
                l += D
        print(power)

main()