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:
#入力
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):
            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)

Submission status: Time Limit Exceeded

Solution code:
data1 = input("")
data1 = data1.split(" ")
h = int(data1[0])
w = int(data1[1])
d = int(data1[2])
a = ["0"]*h
for i in range(h):
    a[i] = input("")
    a[i] = a[i].split(" ")
q = int(input(""))
data2 = ["0"]*q
l = [0]*q
r = [0]*q
m = [0]*q
for i in range(q):
    data2[i] = input("")
    data2[i] = data2[i].split(" ")
    l[i] = int(data2[i][0])
    r[i] = int(data2[i][1])
    while l[i] != r[i]:
        for j in range(h):
            for k in range(w):
                if int(a[j][k]) == l[i]:
                    start_X = k
                    start_Y = j
                    for n in range(h):
                        for o in range(w):
                            if int(a[n][o]) == l[i] + d:
                                m[i] += (abs(start_X-o)+abs(start_Y-n))
                                l[i] += d
for i in range(q):
    print(m[i])

Submission status: Time Limit Exceeded

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

    MAP  = [None] * (H*W+1)
    COST = {}

    for i in range(H):
        for j, str_l in enumerate(input().split()):
            MAP[int(str_l)] = (i, j)

    Q = int(input())

    for i in range(Q):
        L, R = map(int, input().split())
        cost = 0
        keys = COST.keys()
        while L < R:
            try:
                cost += COST[L]
            except:
                COST[L] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
                cost += COST[L]
            L += D
        print(cost)

func()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

MAP  = [None] * (H*W+1)
COST = {}

for i in range(H):
    for j, str_l in enumerate(input().split()):
        MAP[int(str_l)] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    keys = COST.keys()
    while L != R:
        way = '%s,%s' % (L, L+D)
        if way in keys:
            pass
        else:
            COST[way] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
            COST.keys()
        cost += COST[way]
        L    += D
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

MAP  = {}
COST = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        MAP[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    keys = COST.keys()
    while L != R:
        way = '%s,%s' % (L, L+D)
        if way in keys:
            pass
        else:
            COST[way] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
            COST.keys()
        cost += COST[way]
        L    += D
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

MAP  = {}
COST = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        MAP[l] = (i, j)


Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        if '%s,%s' % (L, L+D) in COST.keys():
            pass
        else:
            COST['%s,%s' % (L, L+D)] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
        cost += COST['%s,%s' % (L, L+D)]
        L    += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

MAP  = {}
COST = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        MAP[l] = (i, j)

for start in range(1, H*W+1):
    for stop in range(1, H*W+1):
        COST['%s,%s' % (start, stop)] = abs(MAP[start][0] - MAP[stop][0]) + abs(MAP[start][1] - MAP[stop][1])

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        cost += COST['%s,%s' % (L, L+D)]
        L    += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

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

A = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        A[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

A = [False] * (H*W+1)

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        A[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

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

A = list(range(H*W+1))

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        A[l[j]] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

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

A = [False] * (H * W + 1)

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        A[l[j]] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    start = False
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-



import numpy as np


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

A = []

for i in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    start = False
    while L != R:
        start = np.where(A==L) if start == False else start
        stop  = np.where(A==L+D)
        cost += abs(start[0][0] - stop[0][0]) + abs(abs(start[1][0] - stop[1][0]))
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-



import numpy as np


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

A = []

for i in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = np.where(A==L)
        stop  = np.where(A==L+D)
        cost += abs(start[0][0] - stop[0][0]) + abs(abs(start[1][0] - stop[1][0]))
        L += D
    print(cost, flush=True)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-



import numpy as np


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

A = []

for i in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = np.where(A==L)
        stop  = np.where(A==L+D)
        cost += abs(start[0][0] - stop[0][0]) + abs(abs(start[1][0] - stop[1][0]))
        L += D
    print(cost)

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

sA = [0 for i in range(H*W+1)]

for i in range(len(A)):
        for j in range(len(A[i])):
            sA[A[i][j]] = [i, j]

for lr in LR:
    mp = 0
    l, r = lr[0], lr[1]
    li, lj = sA[l]
    while l != r:
        nextLi, nextLj = sA[l+D]
        mp += abs(nextLi-li) + abs(nextLj-lj)
        l += D
        li, lj = nextLi, nextLj
    print(mp)

Submission status: Time Limit Exceeded

Solution code:
def sr(f):
    for i in range(len(A)):
            for j in range(len(A[i])):
                if A[i][j] == f:
                    return i, j

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

for lr in LR:
    mp = 0
    l, r = lr[0], lr[1]
    li, lj = sr(l)
    while l != r:
        nextLi, nextLj = sr(l+D)
        mp += abs(nextLi-li) + abs(nextLj-lj)
        l += D
        li, lj = nextLi, nextLj
    print(mp)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = [None]*(H*W)

for i in range(H):
    a = map(int,input().split())
    a = list(a)
    for j in range(len(a)):
        A[i*W+j]=a[j]
    
Q = int(input())
S=[]
for _ in range(Q):
    s=0
    L,R = map(int,input().split())    
    for i in range(L,R,D):
        s += abs(A.index(i)//W - A.index(i+D)//W)+abs(A.index(i)%W - A.index(i+D)%W)

    S.append(s)      
for i in S:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = [None]*(H*W)

for i in range(H):
    a = map(int,input().split())
    a = list(a)
    for j in range(len(a)):
        A[i*W+j]=a[j]
    
Q = int(input())

for _ in range(Q):
    s=0
    L,R = map(int,input().split())    
    for i in range(L,R,D):
        s += abs(A.index(i)//W-A.index(i+D)//W)+abs(A.index(i)%W-A.index(i+D)%W) 
          
    print(s)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = [None]*(H*W)
B=A[:]

for i in range(H):
    a = map(int,input().split())
    a = list(a)
    for j in range(len(a)):
        A[i*W+j]=a[j]
        B[i*W+j]=(i,j)
    
Q = int(input())

for _ in range(Q):
    s=0
    L,R = map(int,input().split())    
    for i in range(L,R,D):
        s += abs(B[A.index(i)][0]-B[A.index(i+D)][0])+abs(B[A.index(i)][1]-B[A.index(i+D)][1]) 
          
    print(s)

Submission status: Time Limit Exceeded

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

for l in range(Q):
    s=0
    L,R = map(int,input().split())    
    while L < R:
        s += abs(A[L][0]-A[L+D][0])+abs(A[L][1]-A[L+D][1]) 
        L +=D            
    print(s)

Submission status: Time Limit Exceeded

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

for i in range(H):
    AH = map(int,input().split())
    A.append(list(AH))
Q = int(input())

for l in range(Q):
    s=0
    L,R = map(int,input().split())
    
    while L != R:
        for m in A:
            if L in m:
                i=A.index(m)
                j=m.index(L)
            if L+D in m:
                x=A.index(m)
                y=m.index(L+D)
                
        L +=D
        s += abs(x-i)+abs(y-j)
            
    print(s)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = []
S=[]

for i in range(H):
    AH = map(int,input().split())
    A.append(list(AH))
Q = int(input())

for l in range(Q):
    s=0
    L,R = map(int,input().split())
    
    while L != R:
        for m in A:
            if L in m:
                i=A.index(m)
                j=m.index(L)
            if L+D in m:
                x=A.index(m)
                y=m.index(L+D)
                
        L +=D
        s += abs(x-i)+abs(y-j)
            
    S.append(s)

for i in S:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [[-1] * (H * W + 1) for x in range(H * W + 1)]

def calc(table, l, r):
    if l == r:
        return 0
    if table[l][r] != -1:
        return table[l][r]
    m_ = abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
    ret = m_ + calc(table, l + D, r)
    table[l][r] = ret
    return ret

Q = int(input())
for q in range(Q):
    l, r = [int(x) for x in input().split()]
    print(calc(table, l, r))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [-1] * (H * W + 1)
# def calc(table, l, r, m):
#     if table[l] != -1:
#         return table[l][r]
#     m_ = abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
#     table[l][l+D] = m_
# print(table)

Q = int(input())
for q in range(Q):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        if table[l] == -1:
            table[l] = abs(A[l+D][0] - A[l][0]) + \
                       abs(A[l+D][1] - A[l][1])
        m += table[l]
        l = l + D
    print(m)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)
Q = int(input())
for q in range(Q):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        m += abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
        l = l + D
    print(m)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        m += abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
        l = l + D
    print(m)

Submission status: Time Limit Exceeded

Solution code:
def magic(l,r,d,m):
    ans = 0
    count = 0
    limit = r - l
    while count < limit:
        a = m[l + count]
        b = m[l + count + d]
        ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
        count += d
    return ans

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

m = [0 for _ in range(h*w+1)]

for i in range(h):
    a = [int(x) for x in input().split()]
    for j,k in enumerate(a):
        m[k] = (i+1,j+1)

q = int(input())

ans = []

for _ in range(q):
    l, r = map(int,input().split())
    ans.append(magic(l,r,d,m))

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
A=[]
ax,ay=[0]*(H*W+1),[0]*(H*W+1)
for _ in range(H):
    A.extend(list(map(int,input().split())))
AA=[0]*(H*W+1)

for i in range(1,H*W+1):
    ax[i],ay[i]=divmod(A.index(i),W)

for i in range(D+1,H*W+1):
    AA[i]=AA[i-D]+abs(ax[i]-ax[i-D])+abs(ay[i]-ay[i-D])


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

Submission status: Time Limit Exceeded

Solution code:
# fork from: https://beta.atcoder.jp/contests/abc089/submissions/2174919

import sys
 
def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])
 
def solve(l, r, d, posses):
    s = 0
    for i in range(l, r, d):
        s += uni_norm(posses[i], posses[i+d])
    return s 
 
with sys.stdin as f:
    s_input = f.read()
 
    s_args = s_input.splitlines()
    header = s_args[0].split()
    h = int(header[0])
    w = int(header[1])
    d = int(header[2])
 
    posses = {}
    
    for r in range(h):
        row = s_args[r+1].split()
        for c, s_val in enumerate(row):
            posses[int(s_val)] = (r, c)
 
    #print(posses)
 
    q = int(s_args[h+1])
    res = []
    for i in range(q):
        query = s_args[h+2+i].split()
        res.append(solve(int(query[0]), int(query[1]), d, posses))
 
    for ans in res:
        print(ans)
            
sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#input part
H,W,D = list(map(int, input().split()))
A=[(0,0)]*(H*W)
for i in range(H):
    tmp = list(map(int, input().split()))
    for j in range(W):
        A[tmp[j]-1]=(i+1,j+1)

#create array of pre-calculation
mod = int((H*W)/D)
array_list = np.zeros((D,mod))
for i in range(D):
    x=i
    com = np.zeros(mod)
    for j in range(mod):
        if x+D>=W*H:
            break
        present_loc = A[x]
        next_loc = A[x+D]
        array_list[i][j] = abs(next_loc[0] - present_loc[0]) + abs(next_loc[1] - present_loc[1])
        x+=D
#examination part
Q=int(input())
LR_list=[(0,0)]*Q
for i in range(Q):
    LR_list[i] = list(map(int, input().split()))
for i in range(Q):
    if LR_list[i][0]==LR_list[i][1]:
        print(0)
    else:
        key = LR_list[i][0]%D-1
        L = int((LR_list[i][0]-1)/D)
        R = int((LR_list[i][1]-1)/D)
        # print L
        # print R
        print(int(sum(array_list[key][L:R])))

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int, raw_input().split())
A=[(0,0)]*(H*W)
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]-1]=(i+1,j+1)

#create array of pre-calculation
mod = (H*W)/D
array_list = []
for i in range(D):
    x=i
    com = [0]*(mod)
    for j in range(mod):
        if x+D>=W*H:
            break
        present_loc = A[x]
        next_loc = A[x+D]
        com[j] = abs(next_loc[0] - present_loc[0]) + abs(next_loc[1] - present_loc[1])
        x+=D
    array_list.append(com)
#examination part
Q=int(raw_input())
LR_list=[(0,0)]*Q
for i in range(Q):
    LR_list[i] = map(int, raw_input().split())
for i in range(Q):
    if LR_list[i][0]==LR_list[i][1]:
        print 0
    else:
        key = LR_list[i][0]%D-1
        L = (LR_list[i][0]-1)/D
        R = (LR_list[i][1]-1)/D
        # print L
        # print R
        print sum(array_list[key][L:R])

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int, raw_input().split())
A=[(0,0)]*(H*W)
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]-1]=(i+1,j+1)
Q=int(raw_input())
#examination part
LR_list=[(0,0)]*Q
for i in range(Q):
    LR_list[i] = map(int, raw_input().split())
for i in range(Q):
    mana=0
    L,R = LR_list[i]
    while R - L != 0:
        present_loc = A[L-1]
        next_loc = A[L+D-1]
        mana += abs(next_loc[0] - present_loc[0])
        mana += abs(next_loc[1] - present_loc[1])
        L += D
    print mana

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int, raw_input().split())
A=[(0,0)]*(H*W)
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]-1]=(i+1,j+1)
Q=int(raw_input())
#examination part
LR_list=[]
for i in range(Q):
    LR_list.append(map(int, raw_input().split()))
for i in range(Q):
    mana=0
    L,R = LR_list[i]
    while R - L != 0:
        present_loc = A[L-1]
        next_loc = A[L+D-1]
        mana += abs(next_loc[0] - present_loc[0])
        mana += abs(next_loc[1] - present_loc[1])
        L += D
    print mana

Submission status: Time Limit Exceeded

Solution code:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
empty = []
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    while a != b:
        sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
        a   += d
    empty.append(sum)

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

Submission status: Time Limit Exceeded

Solution code:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
empty = []
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    if c == 0:
        sum = 0
    else:
        for i in range(c):
            sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
            a   += d
    empty.append(sum)

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

Submission status: Time Limit Exceeded

Solution code:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    for i in range(c):
        sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
        a += d
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
def kyori(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])

def adress(x):
    for retu in score_map:
        try:
            _adress = retu.index(x)
            return _adress, score_map.index(retu)
        except:
            continue


height, width, differentiation = map(int, input().split())
score_map = [list(map(int, input().split())) for _ in range(height)]
times_of_exam = int(input())
starts_and_ends = [input().split() for _ in range(times_of_exam)]

for start_and_end in starts_and_ends:
    all_kyori=0
    start=int(start_and_end[0])
    end=int(start_and_end[1])
    for d in range(start,end,differentiation):
        all_kyori+=kyori(adress(d),adress(d+differentiation))
    print(all_kyori)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#input part
H,W,D = map(int, raw_input().split())
A=[(0,0)]*(H*W)
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]-1]=(i+1,j+1)
Q=int(raw_input())
#examination part
LR_list=[]
for i in range(Q):
    LR_list.append(map(int, raw_input().split()))
    # print R - L
for i in range(Q):
    mana=0
    L,R = LR_list[i]
    while R - L != 0:
        # print L+D
        present_loc = A[L-1]
        next_loc = A[L+D-1]
        if next_loc[0] - present_loc[0] < 0:
            mana -= next_loc[0] - present_loc[0]
        else:
            mana += next_loc[0] - present_loc[0]
        if next_loc[1] - present_loc[1] < 0:
            mana -= next_loc[1] - present_loc[1]
        else:
            mana += next_loc[1] - present_loc[1]
        # print mana
        L += D
    print mana

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int, raw_input().split())
A={}
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]]=(i+1,j+1)
Q=int(raw_input())
#examination part
LR_list=[]
for i in range(Q):
    LR_list.append(map(int, raw_input().split()))
    # print R - L
for i in range(Q):
    mana=0
    L,R = LR_list[i]
    while R - L != 0:
        # print L+D
        present_loc = A[L]
        next_loc = A[L+D]
        if next_loc[0] - present_loc[0] < 0:
            mana -= next_loc[0] - present_loc[0]
        else:
            mana += next_loc[0] - present_loc[0]
        if next_loc[1] - present_loc[1] < 0:
            mana -= next_loc[1] - present_loc[1]
        else:
            mana += next_loc[1] - present_loc[1]
        # print mana
        L += D
    print mana

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
listMap = [[int(i) for i in input().split()] for j in range(H)]
ans = []

def returnPos(intVal):
    for i in range(H):
        if intVal in listMap[i]:
            return i,listMap[i].index(intVal)

def useMagic():
    global H,W,D
    Q = int(input())
    for i in range(Q):
        L,R = map(int,input().split())
        # 初期値L=Rの場合、0格納
        if L == R:
            ans.append(0)
            continue
        intStart = returnPos(L)
        intGoal = returnPos(R)
        work = 0

        while intStart != intGoal:
            intTo = returnPos(listMap[intStart[0]][intStart[1]] + D)
            left,right = (intStart[0] + 1) - (intTo[0] + 1), (intStart[1] + 1) - (intTo[1] + 1)
            work += abs(left) + abs(right)
            intStart = intTo
        # while抜けたらwork値を格納
        ans.append(work)

useMagic()
for i in range(len(ans)):
    print(ans[i])

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):
	L,R=list(map(int,input().split()))
	S=[0]*(H*W+1)
	for i in range(D+1,H*W+1):
		S[i]=S[i-D]+abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])
	print(S[R]-S[L])

Submission status: Time Limit Exceeded

Solution code:
import io
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())

    buff = io.StringIO()
    DUP_CASE = {}
    for k in range(Q):
        st, ed = map(int, input().strip().split())
        count = 0
        if st == ed:
            buff.write("0\n")
            continue

        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)
                DUP_CASE[(st, _st + D)] = count
                _st += D
        buff.write(str(count) + "\n")
    print(buff.getvalue())
    buff.close()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import io
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())

    buff = io.StringIO()
    DUP_CASE = {}
    for k in range(Q):
        st, ed = map(int, input().strip().split())
        count = 0
        if st == ed:
            buff.write("0\n")
            continue

        for num in range(ed, st, -1 * D):
            if (st, num) in DUP_CASE:
                _st = num
                count = DUP_CASE[(st, num)]
                break

        if count == 0: # キャッシュなし
            _st = st

        while _st != ed:
            cy, cx = MAP[_st]
            ny, nx = MAP[_st + D]
            count += abs(ny - cy) + abs(nx - cx)
            DUP_CASE[(st, _st + D)] = count
            _st += D
        buff.write(str(count) + "\n")
    print(buff.getvalue())
    buff.close()

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

    DUP_CASE = {}
    for st, ed in CASE:
        count = 0
        if st == ed:
            print(0)
            continue

        for num in range(ed, st, -1 * D):
            if (st, num) in DUP_CASE:
                _st = num
                count = DUP_CASE[(st, num)]
                break

        if count == 0: # キャッシュなし
            _st = st

        while _st != ed:
            cy, cx = MAP[_st]
            ny, nx = MAP[_st + D]
            count += abs(ny - cy) + abs(nx - cx)
            DUP_CASE[(st, _st + D)] = count
            _st += D
        print(count)

if __name__ == '__main__':
    main()