For this python code:
def isSafe(maze, visited, x, y):
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and \
not (maze[x][y] == 0 or visited[x][y])
def find_4path(maze,i,j,dest,visited,a,f,count):
c=0
#new
if (i,j)==dest:
f.append(a)
f[-1]=[n for n in a]
for n in range(len(a)):
a.pop()
#old
#if (i,j)==dest:
#f.append(a)
#a=[]
#c+=1
#print(a,"\n",f,"\n",c)
#if c==count:
#return 1
visited[i][j]=True
if isSafe(maze,visited,i+1,j):
a.append((i+1,j))
print(a)
find_4path(maze,i+1,j,dest,visited,a,f,count)
if isSafe(maze,visited,i-1,j):
a.append((i-1,j))
print(a)
find_4path(maze,i-1,j,dest,visited,a,f,count)
if isSafe(maze,visited,i,j-1):
a.append((i,j-1))
print(a)
find_4path(maze,i,j-1,dest,visited,a,f,count)
if isSafe(maze,visited,i,j+1):
a.append((i,j+1))
print(a)
find_4path(maze,i,j+1,dest,visited,a,f,count)
visited[i][j]=False
if len(a)!=0:
a.pop()
def find(maze, src, dest):
# get source cell (i, j)
i, j = src
# get destination cell (x, y)
x, y = dest
# base case: invalid input
if not maze or not len(maze) or not maze[i][j] or not maze[x][y]:
return 0
# `N × N` matrix
N = len(maze)
# 2D matrix to keep track of cells involved in the current path
visited = [[False for x in range(N)] for y in range(N)]
a=[]
f=[]
count=6
# start from source cell (i, j)
return find_4path(maze, i, j, dest, visited,a,f,count)
if __name__ == '__main__':
maze=[[0,0,1,1,1],[1,1,1,0,1],[1,1,0,1,0],[1,1,0,1,1],[1,1,1,0,0]]
src=(3,0)
dest=(1,4)
print(find(maze, src, dest))
In def find_4path => if (i, j) = dest=> f.append(a) a=[], after matrix f gets its first entry, the code stops working as it should.
After f.append(a), a should become a null matrix, but it does not.
output of 1st and 2nd excution:
[(4, 0)]
[(4, 0), (4, 1)]
[(4, 0), (4, 1), (3, 1)]
...
...
...
[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (0, 4)]
[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (0, 4), (1, 4)]
[]
[[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (0, 4), (1, 4)]]
1
#here matrix `a` should be null matrix i.e. `a=[]`
[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (2, 0)]
[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (2, 0), (1, 0)]
[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (2, 0),(1,0),(1,1)]
...
...
...
[]
[[(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (2, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 3), (0, 4), (1, 4)], [(4, 0), (4, 1), (3, 1), (2, 1), (1, 1), (2, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 3), (0, 4), (1, 4)]]
#here value of `c` should be 2
1
Please point out what is wrong in this code
