https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e03
The above link is the question from CodeJam 2019 Round1A
I have written the following code in python3 it results in TLE for second
TestCase. Do any one know how to solve this? Please help!..
Please do reply if any . Thank you
def calculatePaths(m, n, i, j): # defines knights paths co-ordinates
l = []
if(abs(i - (i + 2) % m) != abs(j - (j + 1) % n) and [(i + 2) % m, (j + 1
) % n] not in l and i != ((i + 2) % m) and j != ((j + 1) % n)):
l.append([(i + 2) % m, (j + 1) % n])
if(abs(i - (i + 2) % m) != abs(j - (j - 1) % n) and [(i + 2) % m, (j - 1
) % n] not in l and i != ((i + 2) % m) and j != ((j - 1) % n)):
l.append([(i + 2) % m, (j - 1) % n])
if(abs(i - (i - 2) % m) != abs(j - (j + 1) % n) and [(i - 2) % m, (j + 1
) % n] not in l and i != ((i - 2) % m) and j != ((j + 1) % n)):
l.append([(i - 2) % m, (j + 1) % n])
if(abs(i - (i - 2) % m) != abs(j - (j - 1) % n) and [(i - 2) % m, (j - 1
) % n] not in l and i != ((i - 2) % m) and j != ((j - 1) % n)):
l.append([(i - 2) % m, (j - 1) % n])
if(abs(i - (i + 1) % m) != abs(j - (j + 2) % n) and [(i + 1) % m, (j + 2
) % n] not in l and i != ((i + 1) % m) and j != ((j + 2) % n)):
l.append([(i + 1) % m, (j + 2) % n])
if(abs(i - (i + 1) % m) != abs(j - (j - 2) % n) and [(i + 1) % m, (j - 2
) % n] not in l and i != ((i + 1) % m) and j != ((j - 2) % n)):
l.append([(i + 1) % m, (j - 2) % n])
if(abs(i - (i - 1) % m) != abs(j - (j + 2) % n) and [(i - 1) % m, (j + 2
) % n] not in l and i != ((i - 1) % m) and j != ((j + 2) % n)):
l.append([(i - 1) % m, (j + 2) % n])
if(abs(i - (i - 1) % m) != abs(j - (j - 2) % n) and [(i - 1) % m, (j - 2
) % n] not in l and i != ((i - 1) % m) and j != ((j - 2) % n)):
l.append([(i - 1) % m, (j - 2) % n])
return l
def isfull(l, m, n): # checks if the path is completed
for i in range(m):
for j in range(n):
if (l[i][j] == 0):
return False
return True
def traverse(l, m, n, i, j, ind): # traversal function
global output
global traversed
path = calculatePaths(m, n, i, j)
tracable = False
for ele in path:
if (ele not in output and i != ele[0] and j != ele[1] and abs
(i-j) != abs(ele[0]-ele[1])):
tracable = True
break
if (isfull(l, m, n)):
traversed = True
print("POSSIBLE")
for ele in output:
print(str(ele[0] + 1)+" "+str(ele[1] + 1))
return
elif (not tracable or ind == n*m):
output[ind-1] = [-1, -1]
return
else:
for k in path:
if(k not in output and not traversed):
output[ind] = k
l[k[0]][k[1]] = 1
traverse(l, m, n, k[0], k[1], ind + 1)
l[k[0]][k[1]] = 0
output[ind] = [-1, -1]
te = int(input())
for i in range(te):
traversed = False
print("Case #" + str(i + 1) + ": ", end="")
m, n = [int(x) for x in input().split()]
output = []
l = []
for j in range(m):
x = []
for k in range(n):
x.append(0)
l.append(x)
for j in range(m*n):
output.append([-1, -1])
for j in range(m):
for k in range(n):
l[j][k] = 0
for j in range(m):
for k in range(n):
paths = calculatePaths(m, n, j, k)
output[0] = [j, k]
l[j][k] = 1
for h in paths:
if(not traversed):
output[1] = [h[0], h[1]]
l[h[0]][h[1]] = 1
traverse(l, m, n, h[0], h[1], 2)
output[1] = [-1, -1]
l[h[0]][h[1]] = 0
l[j][k] = 0
if (not traversed):
print("IMPOSSIBLE")
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/a55c7b39-14d3-4086-979b-dec1de2c7547%40googlegroups.com.
