-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs.py
46 lines (38 loc) · 1.37 KB
/
dfs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from helpers import get_path, offsets, is_legal_pos, read_maze
from stack import Stack
def dfs(maze, start, goal):
stack = Stack()
stack.push(start)
predecessors = {start: None}
while not stack.is_empty():
current_cell = stack.pop()
if current_cell == goal:
return get_path(predecessors, start, goal)
for direction in ["up", "right", "down", "left"]:
row_offset, col_offset = offsets[direction]
neighbour = (current_cell[0] + row_offset, current_cell[1] + col_offset)
if is_legal_pos(maze, neighbour) and neighbour not in predecessors:
stack.push(neighbour)
predecessors[neighbour] = current_cell
return None
if __name__ == "__main__":
# Test 1
maze = [[0] * 3 for row in range(3)]
start_pos = (0, 0)
goal_pos = (2, 2)
result = dfs(maze, start_pos, goal_pos)
assert result == [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
# Test 2
maze = read_maze("mazes/mini_maze_dfs.txt")
for row in maze:
print(row)
start_pos = (0, 0)
goal_pos = (2, 2)
result = dfs(maze, start_pos, goal_pos)
assert result == [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)]
# Test 3
maze = read_maze("mazes/mini_maze_dfs.txt")
start_pos = (0, 0)
goal_pos = (3, 3)
result = dfs(maze, start_pos, goal_pos)
assert result is None