Problem p03426 (python)

Fixed submission:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[] for i in range(D)]

    for i in range(0, H * W):
        A = i + 1
        if len(dp[A % (D)]) == 0:
            dp[A % (D)].append((A, 0))
        else:
            (prev_point, prev_cost)= dp[A % D][len(dp[A % D]) - 1]
            prev_pos = num_dic[prev_point]
            now_pos = num_dic[A]
            dp[A % (D)].append((A, prev_cost +abs(prev_pos[0] - now_pos[0]) + abs(prev_pos[1] - now_pos[1])))

    for test in test_list:
        L = test[0]
        R = test[1]
        if L==R:
            print 0
        else:
            print (dp[L % (D)] [R/(D) - 1 + (1 if R % D != 0 else 0)][1] -
                    (dp[L % (D)] [L/(D) - 1 + (1 if L % D != 0 else 0)][1] ))




if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = [[0 for i in range(300)] for j in range(300)]

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = [[0 for i in range(300)] for j in range(300)]

def dp_search(L, R, D, num_dic):
    global dp
    if dp[L][R] != 0:
        return dp[L][R]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[L][R] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[L][R]

    dp[L][R] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[L][R]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()