Ruudukko

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

for i in range(n):
    l = []
    l.append(input())
    l = [int(i) for i in l[0].split()]
    matrix.append(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}"] = []

            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:
                    mY[i] = [mY[i], True]
                else:
                    mY[i] = [mY[i], False]

                if mX[i] < matrix[pY][pX] and i != pX:
                    mX[i] = [mX[i], True]
                else:
                    mX[i] = [mX[i], False]

                if mY[i][1] == True:
                    coords[f"{pX}:{pY}"].append(f"{pX}:{i}")

                if mX[i][1] == True:
                    coords[f"{pX}:{pY}"].append(f"{i}:{pY}")

    return coords

def bfs(coords=possible_moves(), n=n):
    queue = []
    visited = []
    cache = {}

    lens = 0
    a = 0
    temp = 0

    for i in coords.keys():
        lens += len(coords[i])
        queue.append(i)

    while len(queue) > 0:
        m = queue.pop(0)

        if m in cache:
            #print(' skip:',m,' added:',cache[m][0], end=' _ ')
            #print('extended:', cache[m][1], end=' _ ')
            #print(queue)
            a += cache[m][0]
            queue.extend(cache[m][1])
            continue

        for j in coords[m]:
            #print('j',j)
            temp+=1
            queue.append(j)
            
        cache[m] = [temp,coords[m]]

        
        a+=temp
        temp=0

    print(a + n ** 2)


if __name__ == "__main__":
    bfs()

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