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())
n2c = {i:None for i in range(1, h*w+1)}
for i in range(h):
    i += 1
    for j,v in enumerate(input().split()):
        j = j + 1
        v = int(v)
        n2c[v] = (i,j)


def c(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

q = int(input())
for i in range(q):
    cost = 0
    l,r = map(int, input().split())
    lt = range(l,r+1,d)
    l = list(map(lambda x:n2c[x], lt))
    for i in range(len(l)-1):
        x1,y1 = l[i]
        x2,y2 = l[i+1]
        cost += c(x1,y1,x2,y2)
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
cost = 0
index = 0
for i in range(q):
    cost = 0
    max = int((r[i]-l[i])/d)
    for j in range(max):
        index = l[i]+j*d
        cost += abs(loc[index+d][0]-loc[index][0])
        cost += abs(loc[index+d][1]-loc[index][1])
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
cost = 0
index = 0
for i in range(q):
    cost = 0
    for j in range(int((r[i]-l[i])/d)):
        #print("{}->{}:{}+{}".format(l[i]+j*d,l[i]+(j+1)*d,
            #abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0]),
            #abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])))
        index = l[i]+j*d
        cost += abs(loc[index+d][0]-loc[index][0])
        cost += abs(loc[index+d][1]-loc[index][1])
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
for i in range(q):
    cost = 0
    for j in range(int((r[i]-l[i])/d)):
        #print("{}->{}:{}+{}".format(l[i]+j*d,l[i]+(j+1)*d,
            #abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0]),
            #abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])))
        index = l[i]+j*d
        cost += abs(loc[index+d][0]-loc[index][0])
        cost += abs(loc[index+d][1]-loc[index][1])
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
for i in range(q):
    cost = 0
    for j in range(int((r[i]-l[i])/d)):
        #print("{}->{}:{}+{}".format(l[i]+j*d,l[i]+(j+1)*d,
            #abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0]),
            #abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])))
        cost += abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0])
        cost += abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])
    print(cost)

Submission status: Time Limit Exceeded

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

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

#def find_pos(cur):
#    for x, y in itertools.product(range(h), range(w)):
#        if board[x,y] == cur:
#            return [x, y]

pos_number = [None for _ in range(h*w) ]
for x, y in itertools.product(range(h), range(w)):
    #print(x,y,board[x][y])
    pos_number[board[x][y]-1] = [x,y]
#print(pos_number)

q = int(input())

for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = pos_number[cur-1]
        next_pos = pos_number[next_n-1]
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
h, w, d = list(map(int, input().split()))
#print(h, w, d)

#line1 = input().split()
#h = int(line1[0])
#w = int(line1[1])
#d = int(line1[2])
#print(h,w,d)
board = []
for i in range(h):
    board.append(list(map(int, input().split())))
boardn = np.array(board)

#print(board)

q = int(input())

def find_pos(cur):
    for x, y in itertools.product(range(h), range(w)):
        if boardn[x,y] == cur:
            return [x, y]

for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = find_pos(cur)
        next_pos = find_pos(next_n)
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Time Limit Exceeded

Solution code:
import itertools
h, w, d = list(map(int, input().split()))
#print(h, w, d)

#line1 = input().split()
#h = int(line1[0])
#w = int(line1[1])
#d = int(line1[2])
#print(h,w,d)
board = []
for i in range(h):
    board.append(list(map(int, input().split())))

#print(board)

q = int(input())

def find_pos(cur):
    for x, y in itertools.product(range(h), range(w)):
        if board[x][y] == cur:
            return [x, y]

for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = find_pos(cur)
        next_pos = find_pos(next_n)
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Time Limit Exceeded

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

#line1 = input().split()
#h = int(line1[0])
#w = int(line1[1])
#d = int(line1[2])
#print(h,w,d)
board = []
for i in range(h):
    board.append(list(map(int, input().split())))

#print(board)

q = int(input())

def find_pos(cur):
    for x in range(h):
        for y in range(w):
            if board[x][y] == cur:
                return [x, y]

for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = find_pos(cur)
        next_pos = find_pos(next_n)
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys

if __name__ == '__main__':
    H,W,D = map(int, raw_input().split())
    A = dict()
    for i in range(H):
        a = map(int, raw_input().split())
        for j in range(W):
            A[str(a[j])] = (i+1, j+1)
    Q = input()
    L = []
    R = []
    for i in range(Q):
        l,r = map(int, raw_input().split())
        L.append(l)
        R.append(r)
    for q in range(Q):
        start = L[q]
        end = R[q]
        now = start
        cost = 0
        while now != end:
            cost += abs(A[str(now)][0] - A[str(now+D)][0]) + abs(A[str(now)][1] - A[str(now+D)][1])
            now += D
        print cost

Submission status: Time Limit Exceeded

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]

h,w,d = [int(i) for i in input().split()]
sa = list_1d(h*w+1,[])
for i in range(h):
    a = [int(k) for k in input().split()]
    for j in range(w):
        sa[a[j]] = [i,j]
q = int(input())
lr = [[int(i) for i in input().split()] for i in range(q)]

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    


for i in range(0,q):
    power = 0
    for j in range(lr[i][0],lr[i][1]-d+1,d):
        power += distance_2d(sa[j],sa[j+d])
    print(power)

Submission status: Time Limit Exceeded

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

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    

def search_2d(a,key):
    x = -1
    y = -1
    for i in range(0,len(a)):
        for j in range(0,len(a[0])):
            if a[i][j] == key:
                x = i
                y = j
        if x != -1:
            break
    
    return([x,y])
 
for i in range(0,q):
    power = 0
    for j in range(lr[i][0],lr[i][1]-d+1,d):
        power += distance_2d(search_2d(a,j),search_2d(a,j+d))
    print(power)

Submission status: Time Limit Exceeded

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

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    
def list_1d(d,v):
    return [ v for i in range(d)]
 
def search_2d(a,key):
    x = -1
    y = -1
    for i in range(0,len(a)):
        for j in range(0,len(a[0])):
            if a[i][j] == key:
                x = i
                y = j
        if x != -1:
            break
    
    return([x,y])
 
sa = list_1d(h*w,[])
 
for i in range(0,h*w):
    sa[i] = search_2d(a,i+1)
 
 
 
for i in range(0,q):
    present = lr[i][0]
    goal = lr[i][1]
    power = 0
    while present != goal:
        power += distance_2d(sa[present-1],sa[present+d-1])
        present += d
    print(power)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = [int(i) for i in input().split()]
a = []
for i in range(0,h):
    a.append(input().split())
for i in range(0,h):
    for j in range(0,w):
        a[i][j] = int(a[i][j])
q = int(input())
lr = []
for i in range(0,q):
    lr.append(input().split())
    
def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    
def list_1d(d,v):
    return [ v for i in range(d)]

def search_2d(a,key):
    x = -1
    y = -1
    for i in range(0,len(a)):
        for j in range(0,len(a[0])):
            if a[i][j] == key:
                x = i
                y = j
        if x != -1:
            break
    
    return([x,y])

sa = list_1d(h*w,[])

for i in range(0,h*w):
    sa[i] = search_2d(a,i+1)



for i in range(0,q):
    present = int(lr[i][0])
    goal = int(lr[i][1])
    power = 0
    while present != goal:
        power += distance_2d(sa[present-1],sa[present+d-1])
        present += d
    print(power)

Submission status: Time Limit Exceeded

Solution code:
tmp = list(map(int,input().split()))
H=tmp[0]
W=tmp[1]
D=tmp[2]
mat=[]
for i in range(H):
	mat+=input().split()
Q=int(input())
data=[]
for i in range(Q):
	data+=input().split()
for i in range(Q):
	cons=0
	while data[2*i]!=data[2*i+1]:
		tmp=str(int(data[2*i])+D)
		dex=mat.index(str(data[2*i]))
		dey=mat.index(tmp)
		cons+=(abs(int(dex/W)-int(dey/W))+abs(dex%H-dey%H))
		data[2*i]=tmp
	else:
		print(cons)

Submission status: Time Limit Exceeded

Solution code:
tmp = list(map(int,input().split()))
H=tmp[0]
W=tmp[1]
D=tmp[2]
mat=[]
for i in range(H):
	mat+=list(map(int,input().split()))
Q=int(input())
data=[]
for i in range(Q):
	data+=map(int,input().split())
for i in range(Q):
	cons=0
	while data[2*i]!=data[2*i+1]:
		dex=mat.index(data[2*i])
		dey=mat.index(data[2*i]+D)
		cons+=(abs(int(dex/W)-int(dey/W))+abs(dex%H-dey%H))
		data[2*i]+=D
	else:
		print(cons)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for i in range(q)]
b = [0] * (h * w)
for i in range(h):
        for j in range(w):
                b[f[i][j] - 1] = [i, j]
for i in range(q):
    ans = 0
    for j in range((lr[i][1] - lr[i][0]) // d):
        ans += abs(b[lr[i][0] + d * (j+1) - 1][0] - b[lr[i][0] + d * j - 1][0])
        ans += abs(b[lr[i][0] + d * (j+1) - 1][1] - b[lr[i][0] + d * j - 1][1])
    print(ans)

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)]
b = []
for i in range(1, h * w + 1):
    for j in range(h):
            if a[j].count(i) == 1:
                b.append([j, a[j].index(i)])
for i in range(q):
    ans = 0
    for j in range((lr[i][1] - lr[i][0]) // d):
        ans += abs(b[lr[i][0] + d * (j+1) - 1][0] - b[lr[i][0] + d * j - 1][0])
        ans += abs(b[lr[i][0] + d * (j+1) - 1][1] - b[lr[i][0] + d * j - 1][1])
    print(ans)

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)]
b = []
for i in range(1, h * w + 1):
    for j in range(h):
        for k in range(w):
            if a[j][k] == i:
                b.append([j, k])
for i in range(q):
    ans = 0
    for j in range((lr[i][1] - lr[i][0]) // d):
        ans += abs(b[lr[i][0] + d * (j+1) - 1][0] - b[lr[i][0] + d * j - 1][0])
        ans += abs(b[lr[i][0] + d * (j+1) - 1][1] - b[lr[i][0] + d * j - 1][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_dict = {}
for i in range(H):
    a = input().split()

    for j in range(W):
        mp_dict[int(a[j])] = (i, j)

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

for x in start_end_list:
    abs_sum = 0
    for k in range(int((x[1] - x[0])/D)):
        abs_sum += abs(mp_dict[x[0] + (k+1)*D][0] -  mp_dict[x[0] + (k*D)][0]) + \
                   abs(mp_dict[x[0] + (k+1) * D][1] - mp_dict[x[0] + (k*D)][1])
    print(abs_sum)

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_dict = {}
for i in range(H):
    a = list(map(int, input().split()))

    for j in range(W):
        mp_dict[a[j]] = (i, j)

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

for x in start_end_list:
    abs_sum = 0
    for k in range(((x[1] - x[0])//D)):
        abs_sum += abs(mp_dict[x[0] + (k+1)*D][0] -  mp_dict[x[0] + (k*D)][0]) + \
                   abs(mp_dict[x[0] + (k+1) * D][1] - mp_dict[x[0] + (k*D)][1])
    print(abs_sum)

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_dict = {}
for i in range(H):
    a = list(map(int, input().split()))

    for j in range(W):
        mp_dict[a[j]] = (i, j)

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

def get_index(point_list, mp_dict, W):
    row_list = []
    column_list = []

    row_list = [mp_dict[x][0] for x in point_list]
    column_list = [mp_dict[x][1] for x in point_list]

    row_list_diff = sum([abs(x-y) for x, y in zip(row_list[1:], row_list[:-1])])
    column_list_diff = sum([abs(x - y) for x, y in zip(column_list[1:], column_list[:-1])])

    return row_list_diff+ column_list_diff

def use_mp(row_list, column_list):
    mp = 0
    for i in range(len(row_list)-1):
        mp += abs(row_list[i+1] - row_list[i]) + abs(column_list[i+1] - column_list[i])

    print(mp)

def place_list(start_end_pair, D):
    jump_num = int((start_end_pair[1] - start_end_pair[0]) / D)
    point_list = [start_end_pair[0] + D * n for n in range(jump_num + 1)]

    return point_list

for x in start_end_list:
    abs_sum = 0
    for k in range(((x[1] - x[0])//D)):
        abs_sum += abs(mp_dict[x[0] + (k+1)*D][0] -  mp_dict[x[0] + (k*D)][0]) + \
                   abs(mp_dict[x[0] + (k + 1) * D][1] - mp_dict[x[0] + (k * D)][1])
    print(abs_sum)

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_dict = {}
for i in range(H):
    a = list(map(int, input().split()))

    for j in range(W):
        mp_dict[a[j]] = (i, j)

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

def get_index(point_list, mp_dict, W):
    row_list = []
    column_list = []

    row_list = [mp_dict[x][0] for x in point_list]
    column_list = [mp_dict[x][1] for x in point_list]

    row_list_diff = sum([abs(x-y) for x, y in zip(row_list[1:], row_list[:-1])])
    column_list_diff = sum([abs(x - y) for x, y in zip(column_list[1:], column_list[:-1])])

    return row_list_diff+ column_list_diff

def use_mp(row_list, column_list):
    mp = 0
    for i in range(len(row_list)-1):
        mp += abs(row_list[i+1] - row_list[i]) + abs(column_list[i+1] - column_list[i])

    print(mp)

def place_list(start_end_pair, D):
    jump_num = int((start_end_pair[1] - start_end_pair[0]) / D)
    point_list = [start_end_pair[0] + D * n for n in range(jump_num + 1)]

    return point_list

for x in start_end_list:
    point_list = place_list(x, D)
    print(get_index(point_list, mp_dict, W))

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_list = []
for i in range(H):
    mp_list += list(map(int, input().split()))

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

def get_index(point_list, mp_list, W):
    row_list = []
    column_list = []

    row_list = [mp_list.index(x) // W for x in point_list]
    column_list = [mp_list.index(x) % W for x in point_list]

    row_list_diff = sum([abs(x-y) for x, y in zip(row_list[1:], row_list[:-1])])
    column_list_diff = sum([abs(x - y) for x, y in zip(column_list[1:], column_list[:-1])])

    return row_list_diff+ column_list_diff

def use_mp(row_list, column_list):
    mp = 0
    for i in range(len(row_list)-1):
        mp += abs(row_list[i+1] - row_list[i]) + abs(column_list[i+1] - column_list[i])

    print(mp)

def place_list(start_end_pair, D):
    jump_num = int((start_end_pair[1] - start_end_pair[0]) / D)
    point_list = [start_end_pair[0] + D * n for n in range(jump_num + 1)]

    return point_list

for x in start_end_list:
    point_list = place_list(x, D)
    print(get_index(point_list, mp_list, W))

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ

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

mp_list = []
for i in range(H):
    mp_list += list(map(int, input().split()))

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

def get_index(point_list, mp_list, W):
    row_list = []
    column_list = []

    row_list = [mp_list.index(x) // W for x in point_list]
    column_list = [mp_list.index(x) % W for x in point_list]
    return row_list, column_list

def use_mp(row_list, column_list):
    mp = 0
    for i in range(len(row_list)-1):
        mp += abs(row_list[i+1] - row_list[i]) + abs(column_list[i+1] - column_list[i])

    print(mp)

def place_list(start_end_pair, D):
    jump_num = int((start_end_pair[1] - start_end_pair[0]) / D)
    point_list = [start_end_pair[0] + D * n for n in range(jump_num + 1)]

    return point_list

for x in start_end_list:
    point_list = place_list(x, D)
    row_list, column_list = get_index(point_list, mp_list, W)
    use_mp(row_list, column_list)

Submission status: Time Limit Exceeded

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ

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

mp_list = []
for i in range(H):
    mp_list.append(list(map(int, input().split())))

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

def get_index(point_list, mp_list):
    place = []
    row_list = []
    column_list = []
    for x in point_list:
        for i in range(len(mp_list)):
            if x in mp_list[i]:
                row_list.append(i)
                column_list.append(mp_list[i].index(x))

    return row_list, column_list

def use_mp(row_list, column_list):
    mp = 0
    for i in range(len(row_list)-1):
        mp += abs(row_list[i+1] - row_list[i]) + abs(column_list[i+1] - column_list[i])

    print(mp)

def place_list(start_end_pair, D):
    jump_num = int((start_end_pair[1] - start_end_pair[0]) / D)
    point_list = [start_end_pair[0] + D * n for n in range(jump_num + 1)]

    return point_list

for x in start_end_list:
    point_list = place_list(x, D)
    row_list, column_list = get_index(point_list, mp_list)
    use_mp(row_list, column_list)





# print(mp_list)
# print(start_end)

Submission status: Time Limit Exceeded

Solution code:
#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field = []
for i in range(H):
    field.append(list(map(int, input().split())))

#numberからD動かした時の魔力
move_dict = {}
pre_length = 0
for now_point in range(1, H * W + 1):
    pre_point = now_point - D
    if now_point > D:
        if now_point - D > D:
            pre_length = move_dict[now_point - D]
        for field_h in range(H):
            for field_w in range(W):
                if field[field_h][field_w] == pre_point:
                    pre_h = field_h
                    pre_w = field_w
                    pre_flag = True
                if field[field_h][field_w] == now_point:
                    now_h = field_h
                    now_w = field_w
                    now_flag = True
        move_dict[now_point] = abs(now_h - pre_h) + abs(now_w - pre_w) + pre_length
    else:
        move_dict[now_point] = 0
           
#試験
Q = int(input())
for test in range(Q):
    target = list(map(int, input().split()))
    count = move_dict[target[1]] - move_dict[target[0]]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field = []
for i in range(H):
    field.append(list(map(int, input().split())))

move_dict = {}
now_point = 1
for number in range(1, H * W - D + 1):
    next_point = now_point + D
    now_flag = False
    next_flag = False
    for field_h in range(H):
        for field_w in range(W):
            if field[field_h][field_w] == now_point:
                now_h = field_h
                now_w = field_w
                now_flag = True
            if field[field_h][field_w] == next_point:
                next_h = field_h
                next_w = field_w
                next_flag = True
        if now_flag and next_flag == True:
            break
            
    move_dict[number] = abs(next_h - now_h) + abs(next_w - now_w)
    now_point += 1
           
Q = int(input())
for test in range(Q):
    target = list(map(int, input().split()))
    count = 0
    step = target[0]
    while not step == target[1]:
        start = step
        count += move_dict[start]
        step = start + D
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j
dic2={}    

for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    (_from_,_to_) = (_in_[0],_in_[1])
    if (_from_,_to_) not in dic2:
        _sum_=0
        for j in range(int((_to_-_from_)/D)):
            _sum_ = _sum_ + int(abs(dic[_from_+j*D].real-dic[_from_+j*D+D].real)+abs(dic[_from_+j*D].imag-dic[_from_+j*D+D].imag))
        print(_sum_)
        dic2[(_from_,_to_)] = _sum_
    else:
        print(dic2[(_from_,_to_)])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j

dic3={}
dic2={}    

for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    (_from_,_to_) = (_in_[0],_in_[1])
    if (_from_,_to_) not in dic2:
        _sum_=0
        for j in range(int((_to_-_from_)/D)):
            if _from_+j*D not in dic3:
                n=_from_+j*D-1
                dic3[n+1] = int(abs(dic[n+1].real-dic[n+1+D].real)+abs(dic[n+1].imag-dic[n+1+D].imag))
            _sum_ = _sum_ + dic3[_from_+j*D]
        print(_sum_)
        dic2[(_from_,_to_)] = _sum_
    else:
        print(dic2[(_from_,_to_)])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j


for n in range(H*W-D):
    dic[n+1] = int(abs(dic[n+1].real-dic[n+1+D].real)+abs(dic[n+1].imag-dic[n+1+D].imag))

dic2={}    

for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    (_from_,_to_) = (_in_[0],_in_[1])
    if (_from_,_to_) not in dic2:
        _sum_=0
        for j in range(int((_to_-_from_)/D)):
            _sum_ = _sum_ + dic[_from_+j*D]
        print(_sum_)
        dic2[(_from_,_to_)] = _sum_
    else:
        print(dic2[(_from_,_to_)])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j


for n in range(H*W-D):
    dic[n+1] = int(abs(dic[n+1].real-dic[n+1+D].real)+abs(dic[n+1].imag-dic[n+1+D].imag))
        
for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    _from_,_to_ = _in_[0],_in_[1]
    _sum_=0
    while _to_ != _from_:
        _sum_ = _sum_ + dic[_from_]
        _from_ = _from_ + D
    print(_sum_)

Submission status: Time Limit Exceeded

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

a_dict = {}
for i in range(h):
  r = list(map(int, input().split()))
  for j in range(w):
    a_dict[r[j]] = [i+1, j+1]

q = int(input())

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

for t in test:
  power = 0
  for i in range((t[1]-t[0])//d):
    current = a_dict[t[0]+i*d]
    _next = a_dict[t[0]+(i+1)*d]
    power += abs(current[0] - _next[0]) + abs(current[1] - _next[1])
  print(power)

Submission status: Time Limit Exceeded

Solution code:
#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field = []
for i in range(H):
    field.append(list(map(int, input().split())))
           
Q = int(input())
target = []
for i in range(Q):
    target.append(list(map(int, input().split())))

#動作
for test in range(Q):
    count = 0
    next_point = target[test][0]
    while not next_point == target[test][1]:
        now_point = next_point
        next_point = now_point + D
        for field_h in range(H):
            if now_point in field[field_h] or next_point in field[field_h]:
                for field_w in range(W):
                    if field[field_h][field_w] == now_point:
                        now_h = field_h
                        now_w = field_w
                    if field[field_h][field_w] == next_point:
                        next_h = field_h
                        next_w = field_w
        count += abs(next_h - now_h) + abs(next_w - now_w)
    print(count)