Ruudukko

from collections import defaultdict

# modified BFS
def find_all_parents(G, s):
    Q = [s]
    parents = defaultdict(set)
    while len(Q) != 0:
        v = Q[0]
        Q.pop(0)
        for w in G.get(v, []):
            parents[w].add(v)
            Q.append(w)
    return parents

# recursive path-finding function (assumes that there exists a path in G from a to b)

def find_all_paths(parents, a, b):
    return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]

# G = {'A':['B','C'], 'B':['D'], 'C':['D', 'F'], 'D':['E', 'F'], 'E':['F']}
# some = find_all_paths(find_all_parents(G, 'B'), 'B', 'F')
# print(len(some))

Graph = {}

noOfVertices = int(input())

counter = 1
index = 0
Grid={}
while (counter<=noOfVertices):
    rowNo = counter
    numbers = list(map(int, input().split()))
    coloumnNo = 1
    for coloumnNo in range(1,noOfVertices+1):
        Grid[index] = [numbers[coloumnNo-1],(rowNo,coloumnNo)]
        index=index+1
    counter=counter+1

for index,value in Grid.items():
    Graph[index] = []
    for index2,otherValue in Grid.items():
        if ((value[1][0]==otherValue[1][0] or value[1][1]==otherValue[1][1]) and otherValue[0]<value[0]):
            Graph[index].append(index2)

noOfPaths = 0

for i in range(0,noOfVertices*noOfVertices):
    for i2 in range (0, noOfVertices*noOfVertices):
        some = find_all_paths(find_all_parents(Graph, i), i, i2)
        noOfPaths = noOfPaths + len(some)

print(noOfPaths%(10000000007))

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: TIME LIMIT EXCEEDED

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