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:
def kousin(klist, koho):
    koho2=[]
    for kh in koho:
        tate=kh[0]
        yoko=kh[1]
        tesu=kh[2]
        #RIGHT, LEFT, UP,DOWN
        if clist[tate][yoko]==0:
            if tate==0:
                koho2.append([tate+1, yoko, tesu])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu])
                else:
                    koho2.append([tate, yoko+1, tesu])
                    koho2.append([tate, yoko-1, tesu])
            elif tate==n-1:
                koho2.append([tate-1, yoko, tesu])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu])
                else:
                    koho2.append([tate, yoko+1, tesu])
                    koho2.append([tate, yoko-1, tesu])
            else:
                koho2.append([tate-1, yoko, tesu])
                koho2.append([tate+1, yoko, tesu])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu])
                else:
                    koho2.append([tate, yoko+1, tesu])
                    koho2.append([tate, yoko-1, tesu])
        
        else:
            if tate==0:
                koho2.append([tate+1, yoko, tesu+1])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu+1])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu+1])
                else:
                    koho2.append([tate, yoko+1, tesu+1])
                    koho2.append([tate, yoko-1, tesu+1])
            elif tate==n-1:
                koho2.append([tate-1, yoko, tesu+1])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu+1])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu+1])
                else:
                    koho2.append([tate, yoko+1, tesu+1])
                    koho2.append([tate, yoko-1, tesu+1])
            else:
                koho2.append([tate-1, yoko, tesu+1])
                koho2.append([tate+1, yoko, tesu+1])
                if yoko==0:
                    koho2.append([tate, yoko+1, tesu+1])
                elif yoko==n-1:
                    koho2.append([tate, yoko-1, tesu+1])
                else:
                    koho2.append([tate, yoko+1, tesu+1])
                    koho2.append([tate, yoko-1, tesu+1])
    koho3=[]
    for kh2 in koho2:
        tate=kh2[0]
        yoko=kh2[1]
        tesu=kh2[2]
        if klist[tate][yoko]==tesu+1:
            klist[tate][yoko]=tesu
            koho3.append([tate, yoko, tesu])
        
    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:
import math
import heapq
from collections import deque


class Graph:
    def __init__(self, n):
        self.vertex = list(range(n*n+1))
        # self.edge = {}
        self.adjacent = {v: [] for v in self.vertex}
        self.nuke = {v: False for v in self.vertex}
        for i in range(1, n*(n-1)+1):
            self.add_edge(i, i+n, 1)
        for i in range(1, n*n+1):
            if i%n != 0:
                self.add_edge(i, i+1, 1)
        for i in range(1, n*n+1):
            if i <=  n or i % n == 1 or i % n == 0 or i > n * (n-1):
                self.add_edge(i, 0, 1)

    def add_edge(self, tail, head, weight):
        self.adjacent[tail].append(head)
        # self.edge[tail, head] = weight
        if head != 0:
            self.adjacent[head].append(tail)
            # self.edge[head, tail] = weight

def bfs(G, source, target):
    distance = {v: math.inf for v in G.vertex}
    distance[source] = 0
    reached = {k: False for k in G.vertex}
    reached[source] = True
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in G.adjacent[u]:
            if not reached[v]:
                reached[v] = True
                if G.nuke[v]:
                    distance[v] = distance[u]
                else:
                    distance[v] = distance[u] + 1
                queue.append(v)
            else:
                if G.nuke[v]:
                    alt = distance[u]
                else:
                    alt = distance[u] + 1
                if distance[v] > alt:
                    distance[v] = alt
    return distance[target] - 1


def dijkstra_heap(G, source, target):
    distance = {v: math.inf for v in G.vertex}
    distance[source] = 0
    H = []
    for v in G.vertex:
        heapq.heappush(H, (distance[v], v))
    while H:
        distance_u, u = heapq.heappop(H)
        for v in G.adjacent[u]:
            alt = distance_u + (0 if G.nuke[v] else 1)
            if distance[v] > alt:
                distance[v] = alt
                heapq.heappush(H, (alt, v))
    return distance[target] - 1

n = int(input())
P = map(int, input().split())
G = Graph(n)
ans = 0
for p in P:
    # ca = bfs(G, p, 0)
    ca = dijkstra_heap(G, p, 0)
    ans += ca
    G.nuke[p] = True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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


def escape(F,ys,xs,n):
  if xs==0 or xs==n-1 or ys==0 or ys==n-1:
    return 0

  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),(0,-1),(-1,0)):
      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
  c = escape(F,y,x,n)  
  ans += c
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys


input = sys.stdin.readline

N = int(input())
Order = list(map(int, input().split()))
Maze = [[1] * N for _ in range(N)]
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
ans = 0
for o in Order:
    o -= 1
    sx = o % N
    sy = o // N
    Q = []
    now = (0, sx, sy)
    heapq.heappush(Q, now)
    D = [[False] * N for _ in range(N)]
    D[sy][sx] = True
    while len(Q) > 0:
        fatigue, x, y = heapq.heappop(Q)
        if x < 0 or y < 0 or x >= N or y >= N:
            ans += fatigue
            break
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                heapq.heappush(Q, (fatigue, nx, ny))
            elif D[ny][nx]:
                continue
            else:
                D[ny][nx] = True
                if Maze[ny][nx] != 0:
                    heapq.heappush(Q, (fatigue + 1, nx, ny))
                else:
                    heapq.heappush(Q, (fatigue, nx, ny))

    Maze[sy][sx] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
S = list(map(int, input().split()))
P = [0]*(N**2)
for i in range(N**2):
    P[S[i]-1] = i

def bfs(loc):
    data = [True]*(N**2)
    data[loc] = 1
    s = P[loc]
    stack = [[0, loc]]
    while True:
        d, v = heapq.heappop(stack)
        # 上
        if v-N >= 0:
            if data[v-N]:
                data[v-N] = False
                if s < P[v-N]:
                    heapq.heappush(stack, [d+1, v-N])
                else:
                    heapq.heappush(stack, [d, v-N])
        else:
            return d
        # 左
        if v%N != 0:
            if data[v-1]:
                data[v-1] = False
                if s < P[v-1]:
                    heapq.heappush(stack, [d+1, v-1])
                else:
                    heapq.heappush(stack, [d, v-1])
        else:
            return d
        # 右
        if (v+1)%N != 0 and v != N**2-1:
            if data[v+1]:
                data[v+1] = False
                if s < P[v+1]:
                    heapq.heappush(stack, [d+1, v+1])
                else:
                    heapq.heappush(stack, [d, v+1])
        else:
            return d
        # 下
        if v+N < N**2:
            if data[v+N]:
                data[v+N] = False
                if s < P[v+N]:
                    heapq.heappush(stack, [d+1, v+N])
                else:
                    heapq.heappush(stack, [d, v+N])
        else:
            return d

ans = 0
for i in range(N**2-4):
    ans += bfs(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    P = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    seat=[1]*(N**2)
    ds=((0,1),(0,-1),(1,0),(-1,0))
    count=0
    kei=[-1]*(N**2)
    N2=N**2
    for p in P:
        p-=1
        seat[p]=0
        q=deque([p])
        visited=[False]*N**2
        
        while len(q):
            d,e=divmod(q.popleft(),N2)#ここをpopleftにすると幅優先探索BFSになる
            if visited[e]:continue
            x,y=divmod(e,N)
            if x==0 or x==N-1 or y==0 or y==N-1:
                count+=d
                break
            visited[e]=True
            for dx,dy in ds:
                nx,ny=x+dx,y+dy
                ne=nx*N+ny
                if seat[ne]:
                    q.append(ne+N2*(d+1))
                else:
                    q.appendleft(ne+N2*d)
    print(count)




if __name__ == "__main__":
    main()

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 = min(S[0] - 1, S[1] - 1)
    ans = min(ans, N - S[0], N - S[1])
    T = [[-1] * (s.W + 2) for _ in range(s.H + 2)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      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)
          if ans == 0:
            return ans
          continue
        kk = k + s.L[hh][ww]
        if kk > ans: continue
        if T[hh][ww] > kk or T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = 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]
  t = G.dist(S)
  if t == 0:
    G.L[h + 1][w + 1] = -2
  else:
    ans += t
    G.L[h + 1][w + 1] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
P = list(map(int,input().split()))
for i in range(n**2):
    P[i] -= 1


M = [[] for i in range(n**2)]
DD = [[-1,0],[1,0],[0,1],[0,-1]]
V = [1] * (n**2)
for i in range(n**2):
    x = i//n
    y = i%n
    for d in range(4):
        gx = x + DD[d][0]
        gy = y + DD[d][1]
        if 0 <= gx < n and 0 <= gy < n:
            g = gx*n + gy
            M[i].append(g)

D = [0] * (n**2)
for i in range(n**2):
    x = i//n
    y = i%n
    D[i] = min(x, n-1-x, y, n-1-y)

ans = 0
for i in range(n**2):
    # print(D)
    ans += D[P[i]]
    V[P[i]] = 0
    
    s = 0
    Q = [P[i]]
    while s < len(Q):
        mi = D[Q[s]]
        for j in M[Q[s]]:
            if D[j] > D[Q[s]] + V[Q[s]]:
                Q.append(j)
                D[j] = D[Q[s]] + V[Q[s]]
        s += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
Order = list(map(int, input().split()))
Maze = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        Maze[i][j] = i * N + j + 1
cnt = 1
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
ans = 0
Done = [[-1] * N for _ in range(N)]
for o in Order:
    o -= 1
    sx = o % N
    sy = o // N
    Q = []
    now = (0, sx, sy)
    heapq.heappush(Q, now)
    D = [[False] * N for _ in range(N)]
    D[sy][sx] = True
    while len(Q) > 0:
        fatigue, x, y = heapq.heappop(Q)
        if x < 0 or y < 0 or x >= N or y >= N:
            ans += fatigue
            Done[sy][sx] = fatigue
            break
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                heapq.heappush(Q, (fatigue, nx, ny))
            elif D[ny][nx]:
                continue
            else:
                D[ny][nx] = True
                if Done[ny][nx] != -1:
                    heapq.heappush(Q, (fatigue + Done[ny][nx], -1, -1))
                if Maze[ny][nx] != 0:
                    heapq.heappush(Q, (fatigue + 1, nx, ny))
                else:
                    heapq.heappush(Q, (fatigue, nx, ny))

    Maze[sy][sx] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    P = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    seat=[1]*(N**2)
    ds=((0,1),(0,-1),(1,0),(-1,0))
    count=0
    for p in P:
        p=p-1
        seat[p]=0
        q=deque([(p,0)])
        visited=[False]*N**2
        
        while len(q):
            e,d=q.popleft()#ここをpopleftにすると幅優先探索BFSになる
            if visited[e]:continue
            x,y=divmod(e,N)
            if x==0 or x==N-1 or y==0 or y==N-1:
                count+=d
                break
            visited[e]=True
            for dx,dy in ds:
                nx,ny=x+dx,y+dy
                ne=nx*N+ny
                if seat[ne]:
                    q.append((ne,d+1))
                else:
                    q.appendleft((ne,d))
    print(count)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
seat = [[True]*n for i in range(n)]
lst = list(map(int, input().split()))

def place(m):
  m -= 1
  return [m//n, m%n]

ans = 0

for i in range(n**2):
  
  h = place(lst[i])
  seat[h[0]][h[1]] = False
  score = float('inf')
  
  if h[0] == 0 or h[0] == n-1 or h[1] == 0 or h[1] == n-1:
    continue
    
  sy, sx = h[0], h[1]
  dist = [[-1]*n for _ in range(n)]
  queue = deque([])
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]

  dist[sy][sx] = 0
  queue.appendleft([sy, sx])

  while len(queue) > 0:
    v = queue.popleft() 

    for i in range(4):
    
      next_y, next_x = v[0]+dy[i], v[1]+dx[i]
      if not(0 <= next_y < n) or not(0 <= next_x < n):
        continue 
      if dist[v[0]][v[1]] + seat[next_y][next_x] >= dist[next_y][next_x] >= 0:
        continue
      
      dist[next_y][next_x] = dist[v[0]][v[1]] + seat[next_y][next_x]
    
      if seat[next_y][next_x]:
        queue.append([next_y, next_x])
      else:
        queue.appendleft([next_y, next_x])
    
      if next_y == 0 or next_y == n-1 or next_x == 0 or next_x == n-1:
        score = min(score, dist[next_y][next_x])
      
  ans += score
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)]
    visited[P[i]] = True
    while(not goal):
        #visited = [False for i in range(NN)]
        que = copy.deepcopy(next_que)
        next_que.clear()
        hate = []
        while(len(que) > 0 and not goal):
            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:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    P = list(map(int, readline().split()))
    seat = [[1]*N for _ in range(N)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    for i in range(N**2):
        person = P[i]-1
        sy = person//N
        sx = person%N
        seat[sy][sx] = 0
        if sy==0 or sy==N-1 or sx==0 or sx==N-1:
            continue
        hate = [[INF]*N for _ in range(N)]
        hate[sy][sx]=0
        d = deque([[sy,sx]])
        while d:
            q = d.popleft()
            y = q[0]
            x = q[1]
            if y==0 or y==N-1 or x==0 or x==N-1:
                continue
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0<ny<N-1 and 0<nx<N-1:
                    if hate[ny][nx]>hate[y][x]+seat[ny][nx]:
                        hate[ny][nx] = hate[y][x] + seat[ny][nx]
                        d.append((ny,nx))
                else:
                    if hate[ny][nx]>hate[y][x]+seat[ny][nx]:
                        hate[ny][nx] = hate[y][x] + seat[ny][nx]
        tmp = min(min(hate[0]),min(hate[N-1]),min([x[0] for x in hate]),min([x[N-1] for x in hate]))
        ans += tmp
    print(ans)

if __name__ == '__main__':
    main()

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 + 2) for _ in range(s.H + 2)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      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)
          if ans == 0:
            return ans
          continue
        kk = k + s.L[hh][ww]
        if T[hh][ww] > kk or T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = 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]
  t = G.dist(S)
  if t == 0:
    G.L[h + 1][w + 1] = -2
  else:
    ans += t
    G.L[h + 1][w + 1] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
                koho2.append([[tate+1, yoko], tesu])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            elif tate==n-1:
                koho2.append([[tate-1, yoko], tesu])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
            else:
                koho2.append([[tate-1, yoko], tesu])
                koho2.append([[tate+1, yoko], tesu])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu])
                else:
                    koho2.append([[tate, yoko+1], tesu])
                    koho2.append([[tate, yoko-1], tesu])
        
        else:
            if tate==0:
                koho2.append([[tate+1, yoko], tesu+1])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            elif tate==n-1:
                koho2.append([[tate-1, yoko], tesu+1])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
            else:
                koho2.append([[tate-1, yoko], tesu+1])
                koho2.append([[tate+1, yoko], tesu+1])
                if yoko==0:
                    koho2.append([[tate, yoko+1], tesu+1])
                elif yoko==n-1:
                    koho2.append([[tate, yoko-1], tesu+1])
                else:
                    koho2.append([[tate, yoko+1], tesu+1])
                    koho2.append([[tate, yoko-1], tesu+1])
    koho3=[]
    for kh2 in koho2:
        tate=kh2[0][0]
        yoko=kh2[0][1]
        tesu=kh2[1]
        if klist[tate][yoko]==tesu+1:
            klist[tate][yoko]=tesu
            koho3.append([[tate, yoko], tesu])
        
    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:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    P = list(map(int, readline().split()))
    seat = [[1]*N for _ in range(N)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    for i in range(N**2):
        person = P[i]-1
        sy = person//N
        sx = person%N
        seat[sy][sx] = 0
        if sy==0 or sy==N-1 or sx==0 or sx==N-1:
            continue
        hate = [[INF]*N for _ in range(N)]
        hate[sy][sx]=0
        d = deque([[sy,sx]])
        while d:
            q = d.popleft()
            y = q[0]
            x = q[1]
            if y==0 or y==N-1 or x==0 or x==N-1:
                continue
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0<=ny<N and 0<=nx<N:
                    if hate[ny][nx]>hate[y][x]+seat[ny][nx]:
                        hate[ny][nx] = hate[y][x] + seat[ny][nx]
                        d.append((ny,nx))
        tmp = min(min(hate[0]),min(hate[N-1]),min([x[0] for x in hate]),min([x[N-1] for x in hate]))
        ans += tmp
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline



def ij_to_n(i,j,W):
    return i*W+j

def n_to_ij(n,W):
    return (n//W,n%W)


def n_to_ij_oneoffset(n,W):
    #n+=1
    return (1+(n-1)//W,1+(n-1)%W)


def acinput():
    return list(map(int, input().split(" ")))
       

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))


N=int(input())
H,W=N,N


field = [[-1]*(N+2)]

for i in range(N):
    tmp=[-1]
    
    inputv=[]
    tmp.extend([0]*N)
    tmp.append(-1)           
    field.append(tmp)
    
for i in range(1,N+1):
    for j in range(1,N+1):
        field[i][j]=N*(i-1)+j
        
field.append([-1]*(N+2))

dp=np.full([H+2,W+2],10**9)
state=np.full([H+2,W+2],1)

def propagete(x):
    
    v=dp[x[0]][x[1]]+state[x[0],x[1]]
    #print(x,v)
    for sd in directions:
        nd=x+sd
        if dp[nd[0],nd[1]]>v:
            dp[nd[0],nd[1]]=v
            propagete(nd)
            

for i in range(1,N+1):
    for j in range(1,N+1):
        dp[i,j]=min(i-1,H-i,j-1,W-j)
        
P=acinput()  

dp[1,:]=0
dp[H,:]=0
dp[:,1]=0
dp[:,W]=0

dp[0,:]=0
dp[H+1,:]=0
dp[:,0]=0
dp[:,W+1]=0

res=0
for p in P:
    r=n_to_ij_oneoffset(p,N)
    #print(p,r)
    #print(dp[r[0],r[1]])
    res+=dp[r[0],r[1]]
    state[r[0],r[1]]=0
    propagete(r)
    
print(res)