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

Solution (Python):
from collections import defaultdict

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

Solution (Python):
import sys


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)

if __name__ == '__main__':
    main()

sys.exit()

Solution (Python):
import sys


def main():
    N = int(input())
    P = map(int, input().split())

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)

if __name__ == '__main__':
    main()

sys.exit()

Solution (Python):
def main():
    N = int(input())
    P = map(int, input().split())

    Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

    Sitting = [1] * (N * N)
    Kcount = 0


    def Kcheck(qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            div, mod = divmod(qsn, N)
            if mod: Kcheck(qsn, qsn - 1)
            if mod != N - 1: Kcheck(qsn, qsn + 1)
            if div: Kcheck(qsn, qsn - N)
            if div != N - 1: Kcheck(qsn, qsn + N)

    print(Kcount)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
P = map(int, input().split())

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

Solution (Python):
from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

print(ans)

Solution (Python):
N, *P = map(int, open(0).read().split())

dp = [0] + [min(i, j, N - 1 - i, N - 1 - j) for i in range(N) for j in range(N)]
memo = [1] * (N * N + 1)

def move(fr, to):
    if dp[to] > dp[fr] + memo[fr]:
        dp[to] = dp[fr] + memo[fr]
        S.append(to)

ans = 0
for p in P:
    ans += dp[p]
    memo[p] = 0

    S = [p]
    while S:
        v = S.pop()

        q, r = divmod(v - 1, N)
        if r != 0:
            move(v, v - 1)
        if r != N - 1:
            move(v, v + 1)
        if q < N - 1:
            move(v, v + N)
        if q >= 1:
            move(v, v - N)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

DP=[[0]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        DP[i][j]=min(i,j,N-1-i,N-1-j)

USED=[[1]*N for i in range(N)]
ANS=0

def update(z,w):
    if 0<=z<N and 0<=w<N:
        if DP[z][w]>DP[x][y]+USED[z][w]:
            DP[z][w]=DP[x][y]+USED[z][w]
            Q.append((z,w))
    

for p in P:
    q,r=divmod(p-1,N)
    ANS+=DP[q][r]
    DP[q][r]-=1
    USED[q][r]=0

    Q=[(q,r)]

    while Q:
        x,y=Q.pop()

        update(x+1,y)
        update(x-1,y)
        update(x,y+1)
        update(x,y-1)

print(ANS)

Solution (Python):

import sys


sysread = sys.stdin.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)



import numpy as np


import numba

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

@numba.njit
def run():
    seats = np.zeros((N,N), dtype=np.int16)
    seen = np.zeros((N,N), dtype=np.int8)  
    up, down = 0, N - 1
    dist = 0
    while True:
        seats[up, up:down+1] = dist
        seats[down, up:down+1] = dist
        seats[up:down+1, up] = dist
        seats[up:down+1, down] = dist
        up += 1
        down -= 1
        dist += 1
        if up > down:
            break

    ret = 0
    
    for i in range(N ** 2):
        
        cur_i, cur_j = (P[i] - 1) // N, (P[i] - 1) % N
        ret += seats[cur_i,cur_j]
        seen[cur_i,cur_j] = 1
        stack = [(cur_i, cur_j)]
        while stack:
            cur_i, cur_j = stack.pop()
            for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                n_i = cur_i + i
                n_j = cur_j + j
                del_val = seats[cur_i, cur_j]
                if 0 <= n_i <= N - 1 and 0 <= n_j <= N - 1:
                    if seen[cur_i, cur_j] and del_val < seats[n_i, n_j]:
                        seats[n_i, n_j] = del_val
                        stack.append((n_i, n_j))
                    else:
                        if del_val + 1 < seats[n_i, n_j]:
                            seats[n_i, n_j] = del_val + 1
                            stack.append((n_i, n_j))

    print(ret)


if __name__ == "__main__":
    run()

Solution (Python):

import sys


sysread = sys.stdin.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)



import numpy as np

from collections import deque
import numba

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

@numba.njit
def run():
    seats = np.zeros((N,N), dtype=np.int16)
    seen = np.zeros((N,N), dtype=np.int8)  
    up, down = 0, N - 1
    dist = 0
    while True:
        seats[up, up:down+1] = dist
        seats[down, up:down+1] = dist
        seats[up:down+1, up] = dist
        seats[up:down+1, down] = dist
        up += 1
        down -= 1
        dist += 1
        if up > down:
            break

    ret = 0
    
    for i in range(N ** 2):
        
        cur_i, cur_j = (P[i] - 1) // N, (P[i] - 1) % N
        ret += seats[cur_i,cur_j]
        seen[cur_i,cur_j] = 1
        stack = [(cur_i, cur_j)]
        while stack:
            cur_i, cur_j = stack.pop()
            for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                n_i = cur_i + i
                n_j = cur_j + j
                del_val = seats[cur_i, cur_j]
                if 0 <= n_i <= N - 1 and 0 <= n_j <= N - 1:
                    if seen[cur_i, cur_j]:
                        if del_val < seats[n_i, n_j]:
                            seats[n_i, n_j] = del_val
                            stack.append((n_i, n_j))
                    else:
                        if del_val + 1 < seats[n_i, n_j]:
                            seats[n_i, n_j] = del_val + 1
                            stack.append((n_i, n_j))

    print(ret)


if __name__ == "__main__":
    run()

Solution (Python):
from numba import njit
import numpy as np


def cc_export():
    @njit('(i8, i8, i8[:], i8[:], i8[:], i8)')
    def update(n, w, que, there, cost, pos):
        que[0] = pos
        i, l = 0, 1
        while i < l:
            pos = que[i]
            i += 1
            c = cost[pos]
            t = there[pos]
            k = c + t
            for df in (-w, w, -1, 1):
                pp = pos + df
                if cost[pp] > k:
                    cost[pp] = k
                    que[l] = pp
                    l += 1

    @njit('(i8, i8[:])')
    def main(n, p):
        w = n + 2
        que = np.zeros(4 * w * w, dtype=np.int64)
        there = np.ones(w * w, dtype=np.int64)
        
        
        
        
        
        cost = np.array([
            -1 if i == 0 or i == n + 1 or j == 0 or j == n + 1 else min(
                i - 1, n - i, j - 1, n - j) for j in range(w) for i in range(w)
        ],
                        dtype=np.int64)

        ans = 0
        for pos in p:
            
            
            
            
            
            ans += cost[pos]
            there[pos] = 0
            update(n, w, que, there, cost, pos)
        return ans

    from numba.pycc import CC
    cc = CC('solution')
    cc.export('update', '(i8, i8, i8[:], i8[:], i8[:], i8)')(update)
    cc.export('main', '(i8, i8[:])')(main)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        sys.exit(0)

    def transform(t):
        y, x = divmod(int(t) - 1, n)
        return (y + 1) * (n + 2) + (x + 1)

    from solution import update, main
    n = int(input())
    p = np.array(list(map(transform, input().split())), dtype=np.int64)
    print(main(n, p))

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)



import numpy as np


import numba

def run():
    N = int(input())
    P = np.array((list(map(int, sysread().split()))))
    P -= 1

    @numba.njit("void(i8,i8[:])")
    def proc(N, P):
        ans = 0
        Removed = np.zeros((500, 500), dtype=np.int8)
        Mat = np.zeros((500, 500), dtype=np.int16)
        Dy, Dx = [1, 0, -1, 0], [0, 1, 0, -1]

        for y in range(N):
            for x in range(N):
                Mat[y, x] = min(y, N - 1 - y, x, N - 1 - x)
        
        for i in range(N * N):
            p = P[i]
            y, x = divmod(p, N)
            ans += Mat[y, x]
            Removed[y, x] = 1
            st = [(y, x)]
            while st:
                vy, vx = st.pop()
                vr = Removed[vy, vx]
                val = Mat[vy, vx]
                
                for j in range(4):
                    uy, ux = vy + Dy[j], vx + Dx[j]
                    if not (0 <= uy < N and 0 <= ux < N):
                        continue
                    ur = Removed[uy, ux]
                    if vr:
                        if Mat[uy, ux] >= val + 1:
                            Mat[uy, ux] = val
                            st.append((uy, ux))
                    else:
                        if Mat[uy, ux] >= val + 2:
                            Mat[uy, ux] = val + 1
                            st.append((uy, ux))
        
        
        print(ans)

    proc(N, P)


if __name__ == "__main__":
    run()

Solution (Python):
from numba import njit
import numpy as np

@njit
def main(N, P):
    lista = [1, -1, N, -N]
    d = np.zeros((N, N), dtype=np.int32)
    d = d.ravel()
    sit = np.ones_like(d)
    stack = np.empty_like(d)
    count = 0
    for i in range(N*N):
        d[i] = min(i % N, (N-1-i) % N, i//N, N-1-i//N)
    for player in P:
        sit[player-1] = 0
        count += d[player-1]
        stack[0] = player
        num = 0
        while num >= 0:
            p = stack[num]
            num -= 1
            a = d[p-1]+sit[p-1]
            for i in lista:
                if p+i < 1 or p + i > N*N:
                    continue
                if d[p+i-1] > a:
                    d[p+i-1] = a
                    num += 1
                    stack[num] = p+i
    print(count)

N = int(input())
P = np.array(input().split(), np.int32)

main(N, P)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bfs(src):
    from collections import deque

    que = deque()
    h, w = src
    que.append((dist[h][w], h, w))
    while que:
        cost, h, w = que.popleft()
        if h > 1:
            if dist[h-1][w] > cost:
                dist[h-1][w] = cost
                que.append((cost+seated[h-1][w], h-1, w))
        if h < N-1:
            if dist[h+1][w] > cost:
                dist[h+1][w] = cost
                que.append((cost+seated[h+1][w], h+1, w))
        if w > 1:
            if dist[h][w-1] > cost:
                dist[h][w-1] = cost
                que.append((cost+seated[h][w-1], h, w-1))
        if w < N-1:
            if dist[h][w+1] > cost:
                dist[h][w+1] = cost
                que.append((cost+seated[h][w+1], h, w+1))

N = INT()
P = [p-1 for p in LIST()]

dist = list2d(N, N, 0)
for i in range(N):
    for j in range(N):
        dist[i][j] = min(i, N-i-1, j, N-j-1)

ans = 0
seated = list2d(N, N, 1)
for p in P:
    h, w = divmod(p, N)
    ans += dist[h][w]
    bfs((h, w))
    seated[h][w] = 0
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))

costs = [0]*(N*N)
for i in range(N):
    for j in range(N):
        costs[i*N+j] = min(i,j,N-1-i,N-1-j)
exist = [1]*(N*N)

from collections import deque
ans = 0
for p in P:
    ans += costs[p]
    exist[p] = 0
    q = deque([p])
    while q:
        p = q.popleft()
        y,x = divmod(p,N)
        if x < N-1:
            np = p + 1
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if x > 0:
            np = p - 1
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if y < N-1:
            np = p + N
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if y > 0:
            np = p - N
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1


def main():
    d=[0]*M
    for i in range(N):
        for j in range(N):
            d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
    used=[1]*M
    ans=0
    que=[]
    for p in P:
        ans+=d[p]
        used[p]=0
        que.append(p)
        while que:
            x=que.pop()
            for ddx in (-1,1,-N,N):
                nx=x+ddx
                if 0<=nx<M:
                    if used[x]==0 and d[nx]-d[x]>=1:
                        d[nx]-=1
                        que.append(nx)
                    elif used[x]==1 and d[nx]-d[x]>=2:
                        d[nx]-=1
                        que.append(nx)
    print(ans)

if __name__ == '__main__':
    N=int(input())
    M=N**2
    P=tuple(map(int1,input().split()))
    main()

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=deque()
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]



def main():
	n = int(input())
	nn = [[min(i,j,n-i-1,n-j-1) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]
		is_sit[x][y] = False
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v:
				nn[x-1][y] = v
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v:
				nn[x+1][y] = v
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v:
				nn[x][y-1] = v
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v:
				nn[x][y+1] = v
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)

Solution (Python):
import collections
import sys
input=sys.stdin.readline

def solve():
  n=int(input())
  arr=list(map(int,input().split()))
  cost=[[30000]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      cost[i][j]=min(i,n-(i+1),j,n-(j+1))
  board=[[1]*n for _ in range(n)]
  ans=0
  for val in arr:
    x=(val-1)%n
    y=(val-1)//n
    ans+=cost[y][x]
    board[y][x]=0
    q=collections.deque()
    q.append((x,y))
    while len(q)!=0:
      x,y=q.popleft()
      c=cost[y][x]+board[y][x]
      if x>0 and c<cost[y][x-1]:
        cost[y][x-1]=c
        q.append((x-1,y))    
      if x<n-1 and c<cost[y][x+1]:
        cost[y][x+1]=c
        q.append((x+1,y))    
      if y>0 and c<cost[y-1][x]:
        cost[y-1][x]=c
        q.append((x,y-1))    
      if y<n-1 and c<cost[y+1][x]:
        cost[y+1][x]=c
        q.append((x,y+1))
  print(ans)
solve()

Solution (Python):


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = [min(r, N - 1 - r, c, N - 1 - c) for r in range(N) for c in range(N)]  
    S = [1] * N * N  

    ans = 0
    for pi in p:
        hpi = H[pi]  
        ans += hpi  
        S[pi] = 0  

        
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  
    S = [1] * (N ** 2)  

    ans = 0
    for pi in p:
        hpi = H[pi]  
        ans += hpi  
        S[pi] = 0  

        
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    P = list(map(int, input().split()))
    costs = [-1 for _ in range(N**2)]
    sit = [1 for _ in range(N**2)]
    for i in range(N**2):
        q, mod = divmod(i, N)
        up, down, left, right = q, N-q-1, mod, N-mod-1
        costs[i] = min(up, down, left, right)
    ans = 0
    for p in P:
        ans += costs[p-1]
        sit[p-1] = 0
        que = deque([])
        que.append((p-1, costs[p-1]))
        while len(que) != 0:
            v, d = que.popleft()
            if v > N and costs[v-N] > d:
                costs[v-N] = d
                que.append((v-N, d+sit[v-N]))
            if v < N**2-N-1 and costs[v+N] > d:
                costs[v+N] = d
                que.append((v+N, d+sit[v+N]))
            if v % N != 0 and costs[v-1] > d:
                costs[v-1] = d
                que.append((v-1, d+sit[v-1]))
            if (v+1) % N != 0 and costs[v+1] > d:
                costs[v+1] = d
                que.append((v+1, d+sit[v+1]))
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
n,*p = map(int,sys.stdin.read().split())
dist = [min(a,n-1-a,b,n-1-b) for a in range(n) for b in range(n)]

def update(v,nv):
    if dist[nv] > dist[v] + iru[v]:
        q.append(nv)
        dist[nv] = dist[v] + iru[v]

ans = 0
iru = [1]*n*n
for pi in p:
    pi -= 1
    ans += dist[pi]
    iru[pi] = 0
    q = [pi]
    while q:
        v = q.pop()
        if v%n != n-1: update(v,v+1)
        if v%n: update(v,v-1)
        if v >= n: update(v,v-n)
        if v+n < n*n: update(v,v+n)
print(ans)

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline

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

geta = N+2
G = [0]*(geta*geta)

for v in range(-1-(-N//2), -1, -1):
    l = v+1
    r = N-v
    for i in range(geta):
        G[i*geta+l] = v
        G[i*geta+r] = v
        G[l*geta+i] = v
        G[r*geta+i] = v

for i in range(geta):
    G[i*geta] = -1
    G[i*geta + geta-1] = -1
    G[i] = -1
    G[geta*(geta-1)+i] = -1

Pn = []

for p in P:
    a, b = divmod(p-1, N)
    Pn.append((1+a)*geta+1+b)

DIREC = (1, -1, geta, -geta)
ans = 0
used = [False]*(geta*geta)
for p in Pn:
    ans += G[p]
    res = G[p]
    for d in DIREC:
        res = min(res, G[p+d])
    if G[p] != res:
        G[p] = res
        Q = [p]
        while Q:
            vn = Q.pop()
            for d in DIREC:
                vf = vn + d
                if not used[vf]:
                    if G[vf] > G[vn] + 1:
                        G[vf] = G[vn] + 1
                        Q.append(vf)
                else:
                    if G[vf] > G[vn]:
                        G[vf] = G[vn]
                        Q.append(vf)
                    
    used[p] = True
print(ans)