Ruudukko

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]]
#matrix2 = [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
    LpY = -1
    LpX = -1

    mX = [i for i in matrix[pY]]
    LipY = []

    for j in range(n):
        LipY.append([i[j] for i in matrix])

    #LipY = [mY,str(n+1),str(n+1)]
    #print('LipY:', LipY)

    while pY < n:

        if LpX == n-1:
            mX = [i for i in matrix[pY]]
    #        print('uusi mX', mX)
        
    #    print(pY, ' ', pX)
        mY = LipY[pX]
        
        #mY = [i[pX] for i in matrix]
        #    LipY[pX] = mY
        #else:

       #print(f"mX: {mX} _ mY: {mY}")


        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}")

        LpX = pX
        


        if pX == n - 1:
            pY += 1

        t += 1
        pX += 1

        if pX == n:
            pX = 0

    return coords


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

    a = 0
    temp = 0

    for i in coords.keys():
        queue.append(i)

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

        if m in cache:

            a += cache[m][0]
            queue.extend(cache[m][1])
            continue

        for j in coords[m]:
            temp += 1
            queue.append(j)

        cache[m] = [temp, coords[m]]

        a += temp
        temp = 0
        

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


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