Problem:


Score : 700 points

Problem Statement

Tonight, in your favourite cinema they are giving the movie Joker and all seats are occupied. In the cinema there are N rows with N seats each, forming an N\times N square. We denote with 1, 2,\dots, N the viewers in the first row (from left to right); with N+1, \dots, 2N the viewers in the second row (from left to right); and so on until the last row, whose viewers are denoted by N^2-N+1,\dots, N^2.

At the end of the movie, the viewers go out of the cinema in a certain order: the i-th viewer leaving her seat is the one denoted by the number P_i. The viewer P_{i+1} waits until viewer P_i has left the cinema before leaving her seat.
To exit from the cinema, a viewer must move from seat to seat until she exits the square of seats (any side of the square is a valid exit). A viewer can move from a seat to one of its 4 adjacent seats (same row or same column).
While leaving the cinema, it might be that a certain viewer x goes through a seat currently occupied by viewer y; in that case viewer y will hate viewer x forever. Each viewer chooses the way that minimizes the number of viewers that will hate her forever.

Compute the number of pairs of viewers (x, y) such that y will hate x forever.

Constraints

2 \le N \le 500

The sequence P_1, P_2, \dots, P_{N^2} is a permutation of \{1, 2, \dots, N^2\}.

Input

The input is given from Standard Input in the format

N
P_1 P_2 \cdots P_{N^2}

Output

If ans is the number of pairs of viewers described in the statement, you should print on Standard Output

ans

Sample Input 1

3
1 3 7 9 5 4 8 6 2

Sample Output 1

1

Before the end of the movie, the viewers are arranged in the cinema as follows:

1 2 3
4 5 6
7 8 9

The first four viewers leaving the cinema (1, 3, 7, 9) can leave the cinema without going through any seat, so they will not be hated by anybody.

Then, viewer 5 must go through one of the seats where viewers 2, 4, 6, 8 are currently seated while leaving the cinema; hence he will be hated by at least one of those viewers.

Finally the remaining viewers can leave the cinema (in the order 4, 8, 6, 2) without going through any occupied seat (actually, they can leave the cinema without going through any seat at all).

Sample Input 2

4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

Sample Output 2

3

Sample Input 3

6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30

Sample Output 3

11



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    ans = 10000
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0] - 1][S[1] - 1] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h - 1][w - 1]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh][ww] == -2:
          ans = min(ans, k)
          continue
        kk = k + s.L[hh][ww]
        if T[hh - 1][ww - 1] > kk or T[hh - 1][ww - 1] == -1:
          q.put([hh, ww])
          T[hh - 1][ww - 1] = kk
    return ans


N = int(input())
P = list(map(int, input().split()))

L = [[1 for j in range(N)] for i in range(N)]


G = gridMan(L)
G.makeWall()

ans = 0
for i in P:
  w = (i - 1) % N
  h = (i - w - 1) // N
  S = [h + 1, w + 1]
  ans += G.dist(S)
  G.L[h + 1][w + 1] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import copy
import collections
from collections import deque

N = int(input())
P = list(map(int, input().split()))
P = list(map(lambda x: x - 1, P))

NN = N * N
exist = [True for i in range(NN)]
exist2 = [True for i in range(NN)]
ans = 0
for i in range(NN):
    #print("ans:", ans)
    que = deque()
    next_que = deque()
    next_que.append(P[i])
    goal = False
    #print("start:", P[i] + 1)
    exist[P[i]] = False
    exist2 = copy.deepcopy(exist)
    visited = [False for i in range(NN)]
    while(not goal):
        #visited = [False for i in range(NN)]
        que = copy.deepcopy(next_que)
        visited[P[i]] = True
        hate = []
        while(len(que) > 0):
            p = que.popleft()
            #print(p + 1)
            for nex in [p - 1, p + 1, p + N, p - N]:
                if nex < 0 or nex > NN or p % N == 0 or p % N == N - 1:
                    goal = True
                    break
                if not visited[nex]:
                    if not exist2[nex]:
                        que.append(nex)
                        visited[nex] = True
                    else:
                        next_que.append(nex)
                        hate.append(nex)
        if not goal:
            ans += 1
            #print(list(map(lambda x: x + 1, hate)))
            for h in hate:
                exist2[h] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
p = list(map(int, input().split()))
thea = [[1]*N for i in range(N)]
NN = N**2
ans = 0

def maze(sy, sx):
    dist = [[-1]*N for _ in range(N)]
    dist[sy][sx] = 0
    q = deque()
    q.append((sy,sx))
    while len(q)>0:
        cy, cx = q.popleft()
        # 上下左右のマスの確認,もうちょい綺麗にかけそう
        nl = [(cy-1, cx), (cy, cx-1), (cy+1, cx), (cy, cx+1)]
        for nyx in nl:
            ny, nx = nyx
            if ny >= 0 and ny <= N-1 and nx >= 0 and nx <= N-1:
                if dist[ny][nx] == -1:
                    if thea[ny][nx] == 1:
                        # []から()に変えたらMLE解消した
                        q.append((ny,nx))
                        dist[ny][nx] = dist[cy][cx]+1
                    else:
                        q.appendleft((ny,nx))
                        dist[ny][nx] = dist[cy][cx]
            else:
                return dist[cy][cx]

for i in p:
    i -= 1
    sho = (i)//N
    ama = (i)%N
    if sho == 0 or sho == N-1 or ama == 0 or ama == N-1:
        thea[sho][ama] = 0
    else:
        ans += maze(sho, ama)
        thea[sho][ama] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


DIFFS = [(-1, 0), (0, -1), (0, 1), (1, 0)]


n = int(input())
orders = list(map(int, input().split()))

if n == 2:
    print(0)
    exit(0)

rems = [[True] * n for _ in range(n)]

seats = [[1] * n for _ in range(n)]
for i in range(1, n // 2 + 1):
    for j in range(i, n - i):
        seats[i][j] = seats[n - 1 - i][j] = seats[j][i] = seats[j][n - 1 - i] = i + 1

ans = 0
for order in orders:
    row, col = divmod(order - 1, n)
    ans += seats[row][col] - 1

    rems[row][col] = False

    if row == 0 or row == n - 1 or col == 0 or col == n - 1:
        seats[row][col] = 0
    else:
        min_cost = 1 << 64
        for row_diff, col_diff in DIFFS:
            if 0 <= row + row_diff < n and 0 <= col + col_diff < n:
                min_cost = min(min_cost, seats[row + row_diff][col + col_diff])
            seats[row][col] = min_cost

    opening = deque([(row, col)])
    while opening:
        curr_row, curr_col = opening.popleft()

        for row_diff, col_diff in DIFFS:
            next_row = curr_row + row_diff
            next_col = curr_col + col_diff

            if not (0 <= next_row < n and 0 <= next_col < n):
                continue

            next_cost = seats[curr_row][curr_col] + rems[next_row][next_col]

            if next_cost < seats[next_row][next_col]:
                seats[next_row][next_col] = next_cost
                opening.append((next_row, next_col))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import copy
import collections
from collections import deque

N = int(input())
P = list(map(int, input().split()))
P = list(map(lambda x: x - 1, P))

NN = N * N
exist = [True for i in range(NN)]
exist2 = [True for i in range(NN)]
ans = 0
for i in range(NN):
    #print("ans:", ans)
    que = deque()
    goal = False
    #print("start:", P[i] + 1)
    exist[P[i]] = False
    exist2 = copy.deepcopy(exist)
    while(not goal):
        visited = [False for i in range(NN)]
        que.append(P[i])
        visited[P[i]] = True
        hate = []
        while(len(que) > 0):
            p = que.popleft()
            #print(p + 1)
            for nex in [p - 1, p + 1, p + N, p - N]:
                if nex < 0 or nex > NN or p % N == 0 or p % N == N - 1:
                    goal = True
                    break
                if not visited[nex]:
                    if not exist2[nex]:
                        que.append(nex)
                        visited[nex] = True
                    else:
                        hate.append(nex)
        if not goal:
            ans += 1
            #print(list(map(lambda x: x + 1, hate)))
            for h in hate:
                exist2[h] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
p = inpl()
dic = collections.defaultdict(set)
for i in range(n**2):
    chair = i + 1
    if chair > n:
        dic[chair].add(chair - n)
    else:
        dic[chair].add(0)
    if (chair - 1) % n > 0:
        dic[chair].add(chair - 1)
    else:
        dic[chair].add(0)
    if (chair) % n > 0:
        dic[chair].add(chair + 1)
    else:
        dic[chair].add(0)
    if (chair) <= n * (n - 1):
        dic[chair].add(chair + n)
    else:
        dic[chair].add(0)
ans = 0
exited = set()
exited.add(0)
for i in range(n**2):
    chair = p[i]
    queue = [(0, i) for i in dic[chair]]
    visited = set()
    while True:
        hate, now_chair = heapq.heappop(queue)
        if now_chair in visited:
            continue
        if now_chair == 0:
            ans += hate
            break
        elif now_chair not in exited:
            hate += 1

        for j in dic[now_chair]:
            heapq.heappush(queue, (hate, j))
        visited.add(now_chair)
    exited.add(chair)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

readline = sys.stdin.buffer.readline

def main():
    n = int(readline().rstrip())
    p = list(map(int, readline().split()))
    diag = [-1, 1, n, -n]
    V = (n + 2)**2
    st = [1] * V
    gr = [0] * V
    ans = 0
    for i in range(n):
        for j in range(n):
            gr[i*n + j + n + 1] = min(min(i, j), n-1-max(i, j))
    for v in p:
        v += n
        ans += gr[v]
        st[v] = 0
        c = min([gr[v+dv] + st[v+dv] for dv in diag])
        if c < gr[v]:
            gr[v] = c
        q = deque()
        q.append(v)
        while q:
            v = q.popleft()
            for dv in diag:
                nv = v + dv
                if gr[nv] > gr[v] + st[v]:
                    gr[nv] = gr[v] + st[v]
                    if st[v] > 0:
                        q.append(nv)
                    else:
                        q.appendleft(nv)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
p = list(map(int, input().split()))

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    d = deque()
    d.append((0, pi-1))
    memo = set()

    while d:
        cost, pos = d.popleft()

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if pos + offset not in memo:
                    memo.add(pos + offset)

                    if rev_p[pos + offset] < i:
                        d.appendleft((cost, pos + offset))
                    else:
                        d.append((cost + 1, pos + offset))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def hate(x,y):
    cur_hate = 0
    cur_q = set()
    next_q = set()
    cur_q.add((x,y))
    already = set()
    while True:
        while cur_q:
            x,y = cur_q.pop()
            for i in range(4):
                next_x = x+dx[i]
                next_y = y+dy[i]
                if not (next_x,next_y) in already:
                    if grid[next_y][next_x] == "o":
                        if cur_hate == 0:
                            for x,y in already:
                                grid[y][x] = "o"
                        return cur_hate
                    if grid[next_y][next_x] == "#":
                        next_q.add((next_x,next_y))
                    else:
                        cur_q.add((next_x,next_y))
                    already.add((x,y))
        cur_hate += 1
        cur_q = next_q
        next_q = set()
n = int(input())
grid = []
grid.append(["o"]*(n+2))
for i in range(n):
    grid.append(["o"]+["#"]*n+["o"])
grid.append(["o"]*(n+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    h = hate(x,y)
    ans += h
    if h == 0:
        grid[y][x] = "o"
    else:
        grid[y][x] = "."
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def view(klist):
    for kl in klist:
        print(kl)

def kousin(klist, koho):
    koho2=[]
    for kh in koho:
        tate=kh[0][0]
        yoko=kh[0][1]
        tesu=kh[1]
        if clist[tate][yoko]==0:
            if tate==0:
                if yoko==0:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            elif tate==n-1:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            else:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
                else:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
        
        else:
            if tate==0:
                if yoko==0:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            elif tate==n-1:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            else:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
                else:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
    
    #print(koho2)
    #print("?")
    #print(koho2)
    koho3=[]
    for kh2 in koho2:
        if klist[kh2[0][0]][kh2[0][1]]==kh2[1]+1:
            klist[kh2[0][0]][kh2[0][1]]=kh2[1]
            koho3.append([[kh2[0][0], kh2[0][1]], kh2[1]])
        
    koho=koho3
    
    if koho!=[]:
        kousin(klist, koho)
    

n=int(input())
klist=[]
clist=[]

for i in range(n):
    now=[]
    if i<(n+1)//2:
        for j in range(i):
            now.append(j)
        now+=[i]*(n-i*2)
        #print("!")
        for j in range(i):
            now.append(i-j-1)
    else:
        for j in range(n-i):
            now.append(j)
        now+=[n-i-1]*(i*2-n)
        for j in range(n-i):
            now.append(n-i-j-1)
    klist.append(now)
    clist.append([1]*n)

answer=0

plist = list(map(int, input().split()))
for pl in plist:
    now1=(pl-1)//n
    now2=(pl-1)%n
    answer+=klist[now1][now2]
    clist[now1][now2]=0
    kousin(klist, [ [[now1, now2], klist[now1][now2]] ])
    """
    print(pl, answer)
    view(clist)
    print(",")
    view(klist)
    print(".")
    """
    

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
p = list(map(int, input().split()))

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

ans = 0
for i, pi in enumerate(p):
    d = deque()
    d.append((0, pi-1))
    memo = set()

    while d:
        cost, pos = d.popleft()

        if pos in memo:
            continue

        memo.add(pos)

        if pos < n or pos >= n * (n-1) or pos % n == 0 or pos % n == n-1:
            ans += cost
            break

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                if rev_p[pos + offset] < i:
                    d.appendleft((cost, pos + offset))
                else:
                    if pos+offset not in memo:
                        d.append((cost + 1, pos + offset))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    P = MI()
    emp = [[False] * (N + 1) for _ in range(N + 1)]
    dp = [[inf] * (N + 1) for _ in range(N + 1)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for x in range(1, N + 1):
        for y in range(1, N + 1):
            ax = min(x - 1, N - x)
            ay = min(y - 1, N - y)
            dp[x][y] = min(ax, ay)
    ans = 0
    for i in P:
        x = (i % N)
        y = (i // N) + 1
        if x == 0:
            x += N
            y -= 1
        ans += dp[x][y]
        emp[x][y] = True
        q = deque([(x, y)])
        while q:
            now = q.popleft()
            for j in range(len(dx)):
                nx = now[0] + dx[j]
                ny = now[1] + dy[j]
                if 1 <= nx <= N and 1 <= ny <= N and dp[nx][ny] >= dp[now[0]][now[1]]:
                    dp[nx][ny] = dp[now[0]][now[1]]
                    if emp[nx][ny]:
                        q.append((nx, ny))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = 10**3
n = int(input())
A = list(map(int,input().split()))

F = [[True]*n for _ in range(n)]

def escape(F,ys,xs,n):
  G = [[INF]*n for _ in range(n)]
  G[ys][xs] = 0
  
  que = [(0,ys,xs)] 
  while len(que)>0:
    c,y,x = heapq.heappop(que)    
    if x==0 or x==n-1 or y==0 or y==n-1:
      return c
    for dy,dx in ((0,1),(1,0),(-1,0),(0,-1)):
      nx = dx+x
      ny = dy+y
      
      if G[ny][nx] > G[y][x]:
        G[ny][nx] = G[y][x] + F[ny][nx]        
        heapq.heappush(que,(G[ny][nx],ny,nx))
      
ans = 0
for a in A:
  y = (a-1) //n
  x = (a-1) % n
  F[y][x] = False
  ans += escape(F,y,x,n)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    p = nl()
    diag = [-1, 1, n, -n]
    st = [1]*(n+2)**2
    gr = [0]*(n+2)**2
    ans = 0
    for i in range(n):
        for j in range(n):
            gr[i*n + j + n + 1] = min(min(i, j), n-1-max(i, j))
    for v in p:
        v += n
        ans += gr[v]
        st[v] = 0
        c = gr[v]
        for dv in diag:
            nv = v + dv
            c = min(c, gr[nv] + st[nv])
        gr[v]= c
        q = deque()
        q.append(v)
        while q:
            v = q.popleft()
            for dv in diag:
                nv = v + dv
                if gr[nv] > gr[v] + st[v]:
                    gr[nv] = gr[v] + st[v]
                    if st[v]:
                        q.append(nv)
                    else:
                        q.appendleft(nv)
    print(ans)
    return

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def view(klist):
    for kl in klist:
        print(kl)

def kousin(klist, koho):
    koho2=[]
    for kh in koho:
        tate=kh[0][0]
        yoko=kh[0][1]
        tesu=kh[1]
        if clist[tate][yoko]==0:
            if tate==0:
                if yoko==0:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate+1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            elif tate==n-1:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            else:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
                else:
                    koho2.append([[tate-1, yoko], tesu])
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
                    koho2.append([[tate+1, yoko], tesu])
        
        else:
            if tate==0:
                if yoko==0:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate+1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            elif tate==n-1:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            else:
                if yoko==0:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
                else:
                    koho2.append([[tate-1, yoko], tesu+1])
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
                    koho2.append([[tate+1, yoko], tesu+1])
    
    #print(koho2)
    #print("?")
    #print(koho2)
    koho3=[]
    for kh2 in koho2:
        if klist[kh2[0][0]][kh2[0][1]]==kh2[1]+1:
            klist[kh2[0][0]][kh2[0][1]]=kh2[1]
            koho3.append([[kh2[0][0], kh2[0][1]], kh2[1]])
        
    koho=koho3
    
    if koho!=[]:
        kousin(klist, koho)
    

n=int(input())
klist=[]
clist=[]

for i in range(n):
    now=[]
    if i<(n+1)//2:
        for j in range(i):
            now.append(j)
        now+=[i]*(n-i*2)
        #print("!")
        for j in range(i):
            now.append(i-j-1)
    else:
        for j in range(n-i):
            now.append(j)
        now+=[n-i-1]*(i*2-n)
        for j in range(n-i):
            now.append(n-i-j-1)
    klist.append(now)
    clist.append([1]*n)

#view(klist)

answer=0

#print(clist)

plist = list(map(int, input().split()))
for pl in plist:
    now1=(pl-1)//n
    now2=(pl-1)%n
    answer+=klist[now1][now2]
    clist[now1][now2]=0
    kousin(klist, [ [[now1, now2], klist[now1][now2]] ])
    """
    print(pl, answer)
    view(clist)
    print(",")
    view(klist)
    print(".")
    """
    

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

# 辞書のargmin
def dic_argmin(arg_dic):
	k_ls = list(arg_dic)
	v_ls = [arg_dic[k] for k in k_ls]
	min_idx = np.argmin(v_ls)
	return k_ls[min_idx]

# ダイクストラ法 (低速バージョン)
def slow_dijkstra(graph, start):
	# 距離とキューの初期化
	q = {}
	dist = {}
	for ni, node in enumerate(graph):	# niはnode index
		dist[ni] = math.inf
		q[ni] = 1	# キューに登録
	dist[start] = 0	# 初期位置は距離0
	# 最短距離の探索
	while True:
		# 探索終了条件
		if len(q) == 0: break
		# q残存中で最短距離ノードを取得
		min_ni = dic_argmin({ni: dist[ni] for ni in q})	# 辞書のargmin
		# 確定
		del q[min_ni]
		# 近隣の更新
		min_node = graph[min_ni]
		for neigh in min_node:
			neigh_len = min_node[neigh]	# その隣人までの距離
			# 対象はqに含まれるもののみ
			if neigh not in q: continue
			new_len = dist[min_ni] + neigh_len
			if new_len < dist[neigh]:
				dist[neigh] = new_len
	# 大人の事情により、すべての場所への距離を返す
	return dist

# # 例題
# graph = [
# 	{1:1, 2:10},
# 	{0:1, 2:1},
# 	{0:10, 1: 1}
# ]
# start = 0
# # ダイクストラ法 (低速バージョン)
# dist = slow_dijkstra(graph, start)
# # debug
# print(dist)

# row, col番号から座席番号を返す (範囲外の場合はNone)
def rc2num(r,c,n):
	if r < 0: return None
	if c < 0: return None
	if r >= n: return None
	if c >= n: return None
	return r*n + c

# n×nの観客の退去パスグラフの作成
def make_graph(n):
	graph = []
	for row in range(n):
		for col in range(n):
			d_dic = {}
			for dr,dc in [(1,0), (0,1), (-1,0), (0,-1)]:
				i = rc2num(row+dr,col+dc,n)	# row, col番号から座席番号を返す (範囲外の場合はNone)
				if i is None: continue
				d_dic[i] = 1
			graph.append(d_dic)
	return graph

# 観客が立ち去る (引数を汚染)
def gone_from_graph(graph, p):
	neigh_ls = list(graph[p])
	# 通るコストを0にする (正確にはそのセクションに入るコスト)
	for neigh in neigh_ls:
		graph[neigh][p] = 0

# 読み込み
n, = input_num()
p_ls = input_num()

# 以降、ことわりなき場合は0始まりのインデックスを用いる

# インデックスの読み替え
p_ls = [p-1 for p in p_ls]

# n×nの観客の退去パスグラフの作成
graph = make_graph(n)
# 端の観客番号を列挙 (隣人数を利用)
border_ls = [i for i,e in enumerate(graph)
	if len(e) != 4]

# 観客ひとりずつ計算
ans = 0
for p in p_ls:
	# 観客が立ち去る (引数を汚染)
	gone_from_graph(graph, p)
	# ダイクストラ法 (低速バージョン)
	dist = slow_dijkstra(graph, p)
	# 端の距離を見て最小値を採用
	temp_ans = min([dist[i] for i in border_ls])
	ans += temp_ans

print(ans)