Ruudukko

import copy

n = int(input())
matrix = []
matrix2 = []

for i in range(n):
    l = []
    l.append(input())
    l = [int(i) for i in l[0].split()]
    matrix.append(l)
    matrix2.extend(l)

"""
n = 3
matrix = [[2, 1, 3], [1, 1, 1], [9, 2, 7]]
"""

def possible_moves(matrix=matrix, n=n):
    coords = {}
 
    for pY in range(n):
        for pX in range(n):
            coords[f"{pX}:{pY}"] = []
 
    pY = 0
    pX = 0
    t = 0
    while pY < n:
 
        mY = [i[pX] for i in matrix]
        mX = [i for i in matrix[pY]]
 
        for i in range(n):
            if mY[i] < matrix[pY][pX] and i != pY:
                coords[f"{pX}:{pY}"].append(f"{pX}:{i}")

            if mX[i] < matrix[pY][pX] and i != pX:
                coords[f"{pX}:{pY}"].append(f"{i}:{pY}")
 
        if pX == n - 1:
            pY += 1
 
        t += 1
        pX += 1
 
        if pX == n:
            pX = 0

    return coords

def dfs(start, visited = [],l=[], iteration=0, coords=possible_moves()):
    iteration += 1

    destinations = coords[start]

    visited.append(start)
    
    if start in cache:
        visited.extend(cache[start])
    else:
        #print(visited)
        #print(start, cache, cache[start])

        for destination in destinations:
            dfs(destination,visited,l,iteration)

    return visited

if __name__ == "__main__":

    cache = {}
    a = 0

    for i in possible_moves().keys():
        #print(i)

        visited = []


        v = dfs(i,visited)
        #print(v)
        lis = copy.deepcopy(v)
        lis.remove(i)        
        cache[i] = lis

        a += len(lis)



    #print(cache)

    print((a+n**2) % (10 ** 9 + 7))

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: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED