Ruudukko

# Python3 program for Number of paths
# from one vertex to another vertex
# in a Directed Acyclic Graph
from collections import deque
MAXN = 9
 
# to make graph
v = [[] for i in range(MAXN)]
 
# function to add edge in graph
def add_edge(a, b, fre):
 
	# there is path from a to b.
	v[a].append(b)
	fre[b] += 1
 
# function to make topological sorting
def topological_sorting(fre, n):
	q = deque()
 
	# insert all vertices which
	# don't have any parent.
	for i in range(n):
		if (not fre[i]):
			q.append(i)
 
	l = []
 
	# using kahn's algorithm
	# for topological sorting
	while (len(q) > 0):
		u = q.popleft()
		#q.pop()
 
		# insert front element of queue to vector
		l.append(u)
 
		# go through all it's childs
		for i in range(len(v[u])):
			fre[v[u][i]] -= 1
 
			# whenever the frequency is zero then add
			# this vertex to queue.
			if (not fre[v[u][i]]):
				q.append(v[u][i])
	return l
 
# Function that returns the number of paths
def numberofPaths(source, destination, n, fre):
 
# make topological sorting
	s = topological_sorting(fre, n)
 
	# to store required answer.
	dp = [0]*n
 
	# answer from destination
	# to destination is 1.
	dp[destination] = 1
 
	# traverse in reverse order
	for i in range(len(s) - 1,-1,-1):
		for j in range(len(v[s[i]])):
			dp[s[i]] += dp[v[s[i]][j]]
	return dp
 
 
noOfVertices = int(input())
actualNoOfVertices = noOfVertices*noOfVertices
 
fre = [0]*actualNoOfVertices
 
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():
    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]):
            add_edge(index,index2,fre)
 
fre2 = []
for i in fre:
    fre2.append(i)
 
noOfPaths = 0
 
for i in range(0,noOfVertices*noOfVertices):
    fre.clear()
    for t in fre2:
        fre.append (t)
    some = numberofPaths(0,i,actualNoOfVertices,fre)
    for n in some:
        noOfPaths = noOfPaths + n
 
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: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 88, in <module>
    a...

Test 6

Group: 2, 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 88, in <module>
    a...

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED