Problem p02670 (python)

Fixed submission:
from collections import deque

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

MAP = [min(i, j, N-i-1, N-j-1) for i in range(N) for j in range(N)]

d = [1] * (N ** 2)

ans = 0

def update(np, p):
    if MAP[np] > MAP[p] + d[p]:
        q.append(np)
        MAP[np] = MAP[p] + d[p]

for p in P:
    p -= 1
    
    d[p] = 0
    
    ans += MAP[p]
    
    q = deque()
    
    q.append(p)
    
    while len(q) != 0:
        p = q.popleft()
        if p % N != N-1:
            update(p+1, p)
        if p % N != 0:
            update(p-1, p)
        if p // N != N-1:
            update(p+N, p)
        if p // N != 0:
            update(p-N, p)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(4100000)

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

MAP = [[min(i, j, N-i-1, N-j-1) for i in range(N)] for j in range(N)]

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

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] > MAP[x][y] + d[x][y]:
            MAP[nx][ny] = MAP[x][y] + d[x][y]
            dfs(nx, ny, cnt + d[x][y])

ans = 0

for p in P:
    x = (p-1) // N
    y = (p-1) % N
    d[x][y] = 0
    cnt = float('INF')
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N:
            cnt = min(cnt, MAP[nx][ny] + d[nx][ny])
        else:
            cnt = min(cnt, 0)
    
    ans += MAP[x][y]
    
    MAP[x][y] = cnt
    
    bfs(x, y, cnt)
    

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(4100000)

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

MAP = [[min(i, j, N-i-1, N-j-1) for i in range(N)] for j in range(N)]

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

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] > MAP[x][y] + d[x][y]:
            MAP[nx][ny] = MAP[x][y] + d[x][y]
            dfs(nx, ny, cnt + d[x][y])

ans = 0

for p in P:
    x = (p-1) // N
    y = (p-1) % N
    d[x][y] = 0
    cnt = float('INF')
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N:
            cnt = min(cnt, MAP[nx][ny] + d[nx][ny])
        else:
            cnt = min(cnt, 0)
    
    ans += MAP[x][y]
    
    MAP[x][y] = cnt
    
    bfs(x, y, cnt)
    

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
P = list(map(int,input().split()))

MAP = [[min(i, j, N-i-1, N-j-1) for i in range(N)] for j in range(N)]

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

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def bfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] > MAP[x][y] + d[x][y]:
            MAP[nx][ny] = MAP[x][y] + d[x][y]
            bfs(nx, ny, cnt + d[x][y])

ans = 0

for p in P:
    x = (p-1) // N
    y = (p-1) % N
    d[x][y] = 0
    cnt = float('INF')
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < N and 0 <= ny < N:
            cnt = min(cnt, MAP[nx][ny] + d[nx][ny])
        else:
            cnt = min(cnt, 0)
    
    ans += MAP[x][y]
    
    MAP[x][y] = cnt
    
    bfs(x, y, cnt)
    

print(ans)