'Need Help in improving recursive DFS implementation
I am trying to implement DFS using recursion in Python I am not so good in python but trying to learn it by exploration and experience. The Following is the code I have designed based on my visualization
rowNums = [0, -1, 0, 1]
colNums = [-1, 0, 1, 0]
class Point():
x:int
y:int
def __init__(self, x, y) -> None:
self.x = x
self.y = y
class Node():
coordinates:Point
distance:int
def __init__(self, coords:Point, distance:int):
self.coordinates = coords
self.distance = distance
def isSafe(point:Point, nrow, ncol):
if point.x>=0 and point.x<nrow and point.y>=0 and point.y<ncol:
return True
return False
def DFS(maze:list[list[int]],
src:Point,
dest:Point,
nrow:int,
ncol:int):
visited = []
if maze[src.x][src.y] != 1 or maze[dest.x][dest.y] != 1:
return -1
for i in range(len(maze)):
visited.append([False]*len(maze[i]))
visited[src.x][src.y] = True
def recurTillDeath(node:Node):
point = node.coordinates
if point.x == dest.x and point.y == dest.y:
print("Found it")
return node.distance
else:
print(str(point.x) + " " + str(point.y))
for i in range(0,4):
print("i Values for Point ("+ str(point.x) + " " + str(point.y) +") is "+str(i))
newP = Point(point.x+rowNums[i],point.y+colNums[i])
print(str(newP.x) + " " + str(newP.y))
if isSafe(newP,nrow,ncol) and maze[newP.x][newP.y] != 0 and visited[newP.x][newP.y] != True:
visited[newP.x][newP.y]=True
val = recurTillDeath(Node(newP,node.distance+1))
if val is not None:
return val
return recurTillDeath(Node(src,0))
if __name__ == "__main__":
inputMaze = [[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]]
src = [0, 0]
dest = [3, 3]
srcObject = Point(src[0], src[1])
destObject = Point(dest[0], dest[1])
val = DFS(inputMaze, srcObject, destObject, len(inputMaze), len(inputMaze[0]))
if val == -1:
print("Path does not exist")
else:
print("Length of DFS path is: ", val)
This Code works, But I want to know, Have I used recursion correctly in my recurTillDeath function? Is there a better, more standardized approach to recur?
Edit: as I found solution to my original issue, Modified the question to ask for code improvement help
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
