Reformat maze_search (keon#555)

vdsmitnov52 · Oct 16, 2019 · b09ca79 · b09ca79
1 parent ca21399
commit b09ca79
Showing 1 changed file with 42 additions and 23 deletions.
diff --git a/algorithms/bfs/maze_search.py b/algorithms/bfs/maze_search.py
@@ -1,6 +1,8 @@
+from collections import deque
+
 '''
-BFS time complexity : O(|E|)
-BFS space complexity : O(|V|)
+BFS time complexity : O(|E| + |V|)
+BFS space complexity : O(|E| + |V|)
 
 do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
 
@@ -24,25 +26,42 @@
 the answer is: -1
 '''
 
-def maze_search(grid):
-    dx = [0,0,-1,1]
-    dy = [-1,1,0,0]
-    n = len(grid)
-    m = len(grid[0])
-    q = [(0,0,0)]
-    visit = [[0]*m for _ in range(n)]
-    if grid[0][0] == 0:
+def maze_search(maze):
+    BLOCKED, ALLOWED = 0, 1
+    UNVISITED, VISITED = 0, 1
+
+    initial_x, initial_y = 0, 0
+
+    if maze[initial_x][initial_y] == BLOCKED:
         return -1
-    visit[0][0] = 1
-    while q:
-        i, j, step = q.pop(0)
-        if i == n-1 and j == m-1:
-            return step
-        for k in range(4):
-            x = i + dx[k]
-            y = j + dy[k]
-            if x>=0 and x<n and y>=0 and y<m:
-                if grid[x][y] ==1 and visit[x][y] == 0:
-                    visit[x][y] = 1
-                    q.append((x,y,step+1))
-    return -1
+
+    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
+
+    height, width = len(maze), len(maze[0])
+
+    target_x, target_y = height - 1, width - 1
+
+    queue = deque([(initial_x, initial_y, 0)])
+
+    is_visited = [[UNVISITED for w in range(width)] for h in range(height)]
+    is_visited[initial_x][initial_y] = VISITED
+
+    while queue:
+        x, y, steps = queue.popleft()
+
+        if x == target_x and y == target_y:
+            return steps
+
+        for dx, dy in directions:
+            new_x = x + dx
+            new_y = y + dy
+
+            if not (0 <= new_x < height and 0 <= new_y < width):
+                continue
+
+            if maze[new_x][new_y] == ALLOWED and is_visited[new_x][new_y] == UNVISITED:
+                queue.append((new_x, new_y, steps + 1))
+                is_visited[new_x][new_y] = VISITED
+
+    return -1 
+