Untitled

from collections import deque

def bfs_path(grid, start, goal):
 rows, cols = len(grid), len(grid[0])
 queue = deque([start])
 parent = {start: None}
 moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
    
 while queue:
     r, c = queue.popleft()
     if (r, c) == goal:
         path = []
         while (r, c) is not None:
             path.append((r, c))
             if parent[(r, c)] is None:
                 break
             r, c = parent[(r, c)]
         return path[::-1]
     for dr, dc in moves:
         nr, nc = r + dr, c + dc
         if 0 <= nr < rows and 0 <= nc < cols \
             and grid[nr][nc] == 0 and (nr, nc) not in parent:
                 parent[(nr, nc)] = (r, c)
                 queue.append((nr, nc))
 return None
grid = [
 [0, 0, 0, 1],
 [1, 1, 0, 1],
 [0, 0, 0, 0],
 [0, 1, 1, 0],
] # 0 = free, 1 = obstacle
start, goal = (0, 0), (3, 3)
path = bfs_path(grid, start, goal)

if path:
 print("Path found:", path)
 print("Steps:", len(path) - 1)
else:
 print("No path exists")