Hi, I'm getting WA on TC#5 in MAKEMAZE, my code works fine on sample inputs, comments, and a testcase from a user with WA on the same TC ( [http://discuss.spoj.com/t/getting-wa-on-tc-5-makemaze/8762] ), please help
my code:
def bfs(r, c, onedot, a, beenthere, curr, curc, visited):
# print(curr, curc)
beenthere.append([curr, curc])
if [curr, curc] in onedot: #if [curr, curc] exit or entry point
visited += 1
if len(onedot) == visited:
return 1
if a[curr][curc] != '.': #cannot spread here
return 0
rjes = 0
if curr - 1 >= 0 and [curr - 1, curc] not in beenthere:
if bfs( r, c, onedot, a, beenthere, curr - 1, curc, visited ):
return 1
if curr + 1 <= r - 1 and [curr + 1, curc] not in beenthere:
if bfs( r, c, onedot, a, beenthere, curr + 1, curc, visited ):
return 1
if curc - 1 >= 0 and [curr, curc - 1] not in beenthere:
if bfs( r, c, onedot, a, beenthere, curr, curc - 1, visited ):
return 1
if curc + 1 <= s - 1 and [curr, curc + 1] not in beenthere:
if bfs( r, c, onedot, a, beenthere, curr, curc + 1, visited ):
return 1
return 0
t = int(input())
for _ in range(t):
r, s = [ int(i) for i in input().split() ]
ndot = 0 #num of dots on the edges
onedot = [] #dots on the edges
a = [None] * r
for i in range(r):
a[i] = list(input())
if i == 0 and '.' in a[i]:
ndot += a[i].count('.')
onedot.append([i, a[i].index('.')])
elif i == r - 1 and '.' in a[i]:
ndot += a[i].count('.')
onedot.append([i, a[i].index('.')])
elif a[i][0] == '.':
ndot += 1
onedot.append([i, 0])
elif a[i][s - 1] == '.':
ndot += 1
onedot.append([i, s - 1])
# print(onedot)
if ndot != 2:
print("invalid")
else:
if bfs(r, s, onedot, a, [], onedot[0][0], onedot[0][1], 0):
print("valid")
else:
print("invalid")