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):
import sys
from collections import deque

readline = sys.stdin.readline
ni = lambda: int(readline().rstrip())
nl = lambda: list(map(int, readline().split()))

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

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [((i-1)//n, (i-1) % n) for i in a]
    b = [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]
    sit = [[True for j in range(n)] for i in range(n)]
    ans = 0
    for i, j in a:
        sit[i][j] = False
        ans += b[i][j]
        q = [(i, j, b[i][j])]
        while q:
            x, y, z = q.pop()
            if x != 0:
                if b[x-1][y] > z:
                    b[x-1][y] = z
                    q.append((x-1, y, z+sit[x-1][y]))
            if x != n-1:
                if b[x+1][y] > z:
                    b[x+1][y] = z
                    q.append((x+1, y, z+sit[x+1][y]))
            if y != 0:
                if b[x][y-1] > z:
                    b[x][y-1] = z
                    q.append((x, y-1, z+sit[x][y-1]))
            if y != n-1:
                if b[x][y+1] > z:
                    b[x][y+1] = z
                    q.append((x, y+1, z+sit[x][y+1]))
    print(ans)


main()

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[::1])', cache=True)
def solve(N, P):
    W = N + 2
    dp = np.zeros((W, W), np.int32)
    for _ in range(4):
        dp = dp.T[::-1]
        for n in range(1, (N + 1) // 2 + 1):
            dp[n, n:-n] = n
    filled = np.zeros_like(dp)
    filled[1:-1, 1:-1] = 1
    dp = dp.ravel()
    filled = filled.ravel()
    stack = np.empty_like(dp)
    ans = 0
    for n in P:
        n -= 1
        h, w = divmod(n, N)
        v = (h + 1) * W + (w + 1)
        ans += dp[v] - 1
        filled[v] = 0
        k = min(dp[v - 1], dp[v + 1], dp[v - W], dp[v + W])
        if dp[v] == k:
            return ans
        p = 0
        stack[0] = v
        dp[v] = k
        while p >= 0:
            v = stack[p]
            p -= 1
            for dx in (-1, 1, -W, W):
                w = v + dx
                k = dp[v] + filled[w]
                if dp[w] > k:
                    dp[w] = k
                    p += 1
                    stack[p] = w
    return ans

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

print(solve(N, P))