Ratsun reitit

import sys
from collections import deque

sys.setrecursionlimit(100000)

n = int(input())
# n = 49
shortestpath = {}
adjacencydict = {}
discovered = {}

offsets = ((1, 2), (2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1), (1, -2), (-2, 1))

def getneighbours(node):
    neighbours = set()

    for i in range(8):
        newnode = (node[0]+offsets[i][0], node[1]+offsets[i][1])

        if 0 <= newnode[0] < n and 0 <= newnode[1] < n:
            neighbours.add(newnode)

    return neighbours

for i in range(n):
    for j in range(n):
        shortestpath[(i, j)] = 999999
        adjacencydict[(i, j)] = getneighbours((i, j))
        discovered[(i, j)] = False

start = (0, 0)

# print(adjacencydict)

shortestpath[start] = 0

length = 0

q = deque()



def visit(length):

    if not q:
        return

    node = q.popleft()

    length = shortestpath[node]

    for neighbour in adjacencydict[node]:

        if not discovered[neighbour]:

            discovered[neighbour] = True
            shortestpath[neighbour] = length + 1
            q.append(neighbour)

    visit(length)


def visit2(node, length, seq):
    seq.add(node)
    length += 1
    neighbours = getneighbours(node)
    
    for newnode in neighbours:
        if newnode not in seq:
            if length < shortestpath[newnode]:
                shortestpath[newnode] = length

                visit(newnode, length, seq.copy())
            
#print(getneighbours((2,2)))
seq = set()


q.append(start)
discovered[start] = True
shortestpath[start] = 0

visit(length)
# visit2(start, length, seq)
#print(shortestpath)


for r in range(n):
    row = ""
    for c in range(n):
        row += f"{shortestpath[(r, c)]} "
    
    print(row)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED