Ruudukko

# Python 3 program to count all paths
# from a source to a destination.

# A directed graph using adjacency
# list representation

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def addEdge(self, u, v):

		# Add v to u’s list.
		self.adj[u].append(v)

	# Returns count of paths from 's' to 'd'
	def countPaths(self, s, d):

		# Mark all the vertices
		# as not visited
		visited = [False] * self.V

		# Call the recursive helper
		# function to print all paths
		pathCount = [0]
		self.countPathsUtil(s, d, visited, pathCount)
		return pathCount[0]

	# A recursive function to print all paths
	# from 'u' to 'd'. visited[] keeps track
	# of vertices in current path. path[]
	# stores actual vertices and path_index
	# is current index in path[]
	def countPathsUtil(self, u, d,
					visited, pathCount):
		visited[u] = True

		# If current vertex is same as
		# destination, then increment count
		if (u == d):
			pathCount[0] += 1

		# If current vertex is not destination
		else:

			# Recur for all the vertices
			# adjacent to current vertex
			i = 0
			while i < len(self.adj[u]):
				if (not visited[self.adj[u][i]]):
					self.countPathsUtil(self.adj[u][i], d,
										visited, pathCount)
				i += 1

		visited[u] = False

noOfVertices = int(input())

# Movement = {}
# if (noOfVertices == 3):
# 	Movement = {1:[2,3,4,7], 2:[1,3,5,8], 3:[1,2,6,9], 4:[1,5,6,7], 5: [2,4,6,8], 6:[3,4,5,9], 7:[1,4,8,9], 8: [2,5,7,9], 9: [3,6,7,8]}

# elif (noOfVertices==2):
# 	Movement = {1: [2,3], 2:[1,4], 3:[1,4], 4:[2,3]}

# elif (noOfVertices==1):
# 	print (1)
# 	exit()

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

g = Graph(noOfVertices*noOfVertices)

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]):
            g.addEdge(index,index2)

noOfPaths = 0
	
for coordinate,value in Grid.items():
    for otherCoordinate,otherValue in Grid.items():
        noOfPaths = noOfPaths + g.countPaths(coordinate,otherCoordinate)

print (noOfPaths)

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