Skip to content
TheChatArchiveThe Chat Archive
Step 3.5 Flash· unknownHugging Face Frontier Reasoning Traces

You are given a 2D grid representing a maze with empty cells and walls. Find the…

  1. User

    You are given a 2D grid representing a maze with empty cells and walls. Find the shortest path from a start cell to an end cell. Please what algorithm is perfectly suited for finding the shortest path in an unweighted grid, write a function that solves this problem using Breadth-First Search (BFS), how do you keep track of visited cells to avoid infinite loops, and how can you modify the algorithm to reconstruct the actual path, not just its length.

  2. Assistant

    We are given a 2D grid representing a maze. The grid has empty cells (which we can traverse) and walls (which we cannot). We need to find the shortest path from a start cell to an end cell. Since the grid is unweighted (each step has the same cost), BFS is perfectly suited because it explores all nodes at the present depth before moving on to nodes at the next depth level. Steps:

    1. We'll use a queue for BFS.
    2. We need to mark visited cells to avoid revisiting and infinite loops. We can use a visited matrix (same size as grid) or a set of visited coordinates.
    3. To reconstruct the path, we can keep a parent dictionary (or a predecessor matrix) that records from which cell we came to the current cell.

    However, note: we are in a grid, so we can move in 4 directions (up, down, left, right) unless specified otherwise.

    Let's assume: grid: 2D list, where grid[i][j] is 0 for empty and 1 for wall, or maybe we have a convention? Let's say 0 is empty, 1 is wall. start: (start_row, start_col) end: (end_row, end_col)

    Steps for BFS:

    Initialize: queue = collections.deque() visited = set() or a 2D list of booleans. parent = {} # to store the parent of each cell, so we can backtrack the path.

    We start by marking the start cell as visited and enqueue it.

    While queue is not empty: pop the current cell. if current cell is the end, then break and reconstruct the path.

      For each of the 4 neighbors (up, down, left, right):
          if the neighbor is within grid bounds, is empty (not a wall), and not visited:
             mark it visited, set its parent to the current cell, and enqueue.
    

    If we reach the end, we can reconstruct the path by backtracking from end to start using the parent dictionary.

    If the queue is empty and we haven't reached the end, then there's no path.

    Let's code accordingly.

    However, note: we might want to return the path as a list of cells from start to end, or just the length? The problem says: "find the shortest path", so we want the actual path.

    Let's design the function:

    def shortest_path(grid, start, end): ...

    We assume grid is a list of lists, start and end are tuples (row, col).

    We'll return the path as a list of tuples from start to end, or None if no path exists.

    Implementation:

    We can use a visited matrix of the same size as grid, initialized to False.

    Alternatively, we can use a set for visited.

    Directions: [(0,1), (1,0), (0,-1), (-1,0)] for right, down, left, up.

    We also need to check if the start or end is a wall? In that case, we should return None.

    Steps:

    if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1: return None

    Then, initialize:

    visited = [[False]*len(grid[0]) for _ in range(len(grid))] parent = {} # key: (row, col), value: (parent_row, parent_col)

    queue = deque([start]) visited[start[0]][start[1]] = True

    while queue: current = queue.popleft() if current == end: break

        for d in directions:
            next_row = current[0] + d[0]
            next_col = current[1] + d[1]
            if 0 <= next_row < len(grid) and 0 <= next_col < len(grid[0]) and not visited[next_row][next_col] and grid[next_row][next_col] == 0:
                visited[next_row][next_col] = True
                parent[(next_row, next_col)] = current
                queue.append((next_row, next_col))
    

    If we broke because of finding the end, then we reconstruct:

        path = []
        current = end
        while current != start:
            path.append(current)
            current = parent[current]
        path.append(start)
        path.reverse()
    
        return path
    

    Else, return None.

    But note: what if the start and end are the same? Then we break immediately and the path will be [start] which is correct.

    However, we must check that the start is not a wall? We did that above.

    But what if the end is the same as start and it's a wall? Then we return None because we check at the beginning.

    Alternatively, we can handle the start and end being the same and not a wall by returning [start] immediately.

    Let's adjust:

    if start == end and grid[start[0]][start[1]] == 0: return [start]

    But we already check for walls. So:

    if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1: return None

    Then if start == end, we still run the BFS? Actually, we can avoid the BFS if start==end and it's not a wall.

    Alternatively, we can let the BFS handle it: we enqueue start, then pop it and check if it's end -> yes, then break and reconstruct.

    But note: in the BFS, when we pop the start, we check if it's end. Then we break and then we reconstruct. That works.

    However, we don't set parent for start. So when we backtrack, we stop when current==start. That's okay because we append start at the end.

    But note: the parent dictionary does not have an entry for start. So when current becomes start, we break the while loop and then append start.

    That works.

    However, what if there's no path? Then we never break and the queue becomes empty. Then we return None.

    Let's code accordingly.

    But note: we are using a visited matrix and we mark the start as visited at the beginning.

    One more thing: we are only moving in 4 directions. If we want 8 directions, we change the directions list.

    Let's stick to 4.

    Let's code accordingly.

    However, note: the grid might be represented with different conventions. Let's assume 0 is empty and 1 is wall.

    We'll write the function accordingly.

    But wait: the problem says "empty cells and walls". We assume empty is traversable and wall is not.

    We are given a 2D grid. We don't know the exact representation? Let's assume:

        grid[i][j] == 0 -> empty
        grid[i][j] == 1 -> wall
    

    But what if they use other values? We can have a parameter for empty value? But the problem doesn't specify.

    Let's stick to 0 and 1.

    Alternatively, we can have a function that takes a grid and two cell values: one for empty and one for wall? But the problem says "empty cells and walls", so we assume 0 and 1.

    However, to be safe, we can let the user specify? But the problem doesn't say.

    Since the problem says "representing a maze with empty cells and walls", we assume 0 for empty and 1 for wall.

    But let me note: sometimes mazes use other representations. We can make it general by having a parameter empty and wall? But the problem doesn't specify.

    Since the problem is about BFS and grid, we'll assume:

        if grid[r][c] == 0 -> empty
        else -> wall
    

    But wait, what if there are other numbers? We don't know. So let's stick to the problem: it says empty cells and walls. We assume 0 and 1.

    Alternatively, we can change the condition to:

        if grid[next_row][next_col] == 0:   # 0 is empty
    

    But what if the grid uses True/False? We don't know.

    Since the problem is given as a 2D grid, and we are to code, let's assume:

        empty cell: 0
        wall: 1
    

    We'll write accordingly.

    However, to make it more general, we can have:

        def is_empty(grid, row, col):
            return grid[row][col] == 0
    

    But let's keep it simple.

    Code:

    We'll use collections.deque.

    Steps:

    import collections

    def shortest_path(grid, start, end): rows = len(grid) cols = len(grid[0])

        # Check if start or end is a wall
        if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1:
            return None
    
        # If start equals end, then we are already there.
        if start == end:
            return [start]
    
        directions = [(0,1), (1,0), (0,-1), (-1,0)]  # right, down, left, up
    
        visited = [[False]*cols for _ in range(rows)]
        parent = {}
    
        queue = collections.deque()
        queue.append(start)
        visited[start[0]][start[1]] = True
    
        while queue:
            current = queue.popleft()
            if current == end:
                break
    
            for d in directions:
                next_row = current[0] + d[0]
                next_col = current[1] + d[1]
                if 0 <= next_row < rows and 0 <= next_col < cols:
                    if not visited[next_row][next_col] and grid[next_row][next_col] == 0:
                        visited[next_row][next_col] = True
                        parent[(next_row, next_col)] = current
                        queue.append((next_row, next_col))
    
        # If we found the end, then reconstruct the path
        if end in parent or start == end:   # note: if start==end we already returned, so here end must be in parent or we didn't break by finding end?
            # Actually, we break when current==end. Then we have parent for end? We set parent for a node when we first visit it.
            # So when we break, we have parent for end? Not necessarily: if we break at the start (which we already handled) then no parent for start? But we handled start==end.
            # So now, if we broke because of end, then end is in parent? Yes, because we set parent when we visit a node (and we visit end when we come from a neighbor).
            # But what if the start is the end? We already returned. So now, we broke because of end, and we have parent for end.
    
            # However, note: we break when current==end, and at that point we have not set parent for end? Wait, we set parent for a node when we visit it from a neighbor.
            # How did we get to end? We must have visited it from a neighbor, so we set parent for end when we visited it. So yes, end is in parent.
    
            path = []
            current = end
            while current != start:
                path.append(current)
                current = parent[current]
            path.append(start)
            path.reverse()
            return path
        else:
            return None
    

    But wait: what if the end is never reached? Then we break the while loop when queue is empty, and then we check if end is in parent? It won't be, so we return None.

    However, note: we break the while loop in two ways: either we break because we found end, or the queue becomes empty.

    So after the while, we check if we have the end in the parent dictionary? But what if the start is the end? We already handled that.

    But note: if the start is the end, we returned early. So in the while loop, we only break when we found the end? Actually, we break when current==end.

    So if we break because of that, then we have parent for end? Yes, because we set parent for end when we visited it (from some neighbor). But wait, what if the end is the start? We already handled.

    However, there's a catch: we set parent for a node when we visit it from a neighbor. So the start node does not have a parent. But we don't need to backtrack from start.

    So the reconstruction:

        current = end
        while current != start:
            path.append(current)
            current = parent[current]   # this will eventually be start because we have a path.
    
        Then we append start and reverse.
    

    But what if the end is the start? We don't enter the while loop and then we append start and reverse? Actually, we already returned for start==end.

    So it's safe.

    However, what if the end is not in the parent dictionary? That means we never reached it. But note: we break when current==end, so if we break, then current is end and we have set parent for end? Not necessarily: we set parent for a node when we first visit it. We visit end when we come from a neighbor. So if we break at end, we must have set parent for end at the time we visited it (which was when we enqueued it). So yes, end is in parent.

    But wait: what if the end is the start? Then we don't set parent for start and we break immediately? Actually, we break when current==end, and current is start. So we break and then we try to reconstruct. But we already returned for start==end? We have an early return for start==end, so we don't get to the while loop in that case.

    So the code is safe.

    However, there's a scenario: we break when current==end, but what if the end is not in the parent dictionary? That can happen only if we never set parent for end. But we set parent for a node when we visit it. How did we get to end? We must have visited it from a neighbor, so we set parent for end. So it's in parent.

    But what if the end is the start? Then we break at the first pop? And then we don't have parent for start? But we already returned for start==end.

    So we are safe.

    Let's test with a simple grid:

        grid = [[0,0,0],
                [0,1,0],
                [0,0,0]]
        start = (0,0)
        end = (2,2)
    
        We should get a path.
    

    However, note: we are using a visited matrix. We mark a cell as visited when we first enqueue it. That's correct for BFS.

    But what about multiple paths? BFS guarantees the shortest path in terms of number of steps.

    We are done.

    However, note: the problem says "unweighted grid", so BFS is correct.

    Let me adjust: what if the grid is given as a list of strings? The problem says 2D grid, so we assume list of lists.

    But to be safe, we can convert? No, we assume the input is as described.

    Let's write the code accordingly.

    One more thing: we are using a matrix for visited. We can also use a set, but a matrix is more efficient for grids.

    We'll use a matrix.

    Now, what about the directions? We assume 4-connected.

    If we want 8-connected, we change the directions.

    But the problem doesn't specify, so we assume 4.

    Code:

    We'll import collections.

    Let me write the code accordingly.

    However, note: the grid might be large. We are using BFS which is O(n*m) in the worst case.

    That's acceptable.

    Let's write the function.

    But wait: what if the grid is 1x1? Then we return [start] if it's empty.

    We handle that with the early return.

    Now, let's code. For finding the shortest path in an unweighted grid (where each step has equal cost), Breadth-First Search (BFS) is perfectly suited because it explores all positions at the current distance from the start before moving to positions one step further, guaranteeing the shortest path is found first.


    Key Points of BFS for Grids

    1. Queue-based exploration – Processes cells in FIFO order.
    2. Visited tracking – Prevents revisiting cells and infinite loops.
    3. Parent tracking – Allows reconstruction of the actual path.
    4. 4-directional movement – Typically up/down/left/right (adjustable).

    Implementation

    from collections import deque
    
    def shortest_path(grid, start, end):
        """
        Find the shortest path from start to end in a 2D grid using BFS.
        
        Args:
            grid: 2D list where 0 = empty (traversable), 1 = wall (blocked)
            start: tuple (row, col) of starting cell
            end: tuple (row, col) of target cell
        
        Returns:
            List of cells from start to end (inclusive) representing the shortest path,
            or None if no path exists.
        """
        rows, cols = len(grid), len(grid[0])
        
        # Validate start/end are within bounds and not walls
        if not (0 <= start[0] < rows and 0 <= start[1] < cols and grid[start[0]][start[1]] == 0):
            return None
        if not (0 <= end[0] < rows and 0 <= end[1] < cols and grid[end[0]][end[1]] == 0):
            return None
        if start == end:
            return [start]
        
        # Directions: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        # visited matrix to avoid revisiting cells
        visited = [[False] * cols for _ in range(rows)]
        visited[start[0]][start[1]] = True
        
        # parent dictionary to reconstruct path: child -> parent
        parent = {}
        
        queue = deque([start])
        
        while queue:
            current = queue.popleft()
            
            if current == end:
                # Reconstruct path by backtracking from end to start
                path = []
                while current != start:
                    path.append(current)
                    current = parent[current]
                path.append(start)
                path.reverse()
                return path
            
            for dr, dc in directions:
                r, c = current[0] + dr, current[1] + dc
                if (0 <= r < rows and 0 <= c < cols and 
                    not visited[r][c] and grid[r][c] == 0):
                    visited[r][c] = True
                    parent[(r, c)] = current  # Track where we came from
                    queue.append((r, c))
        
        return None  # No path found
    

    How We Avoid Infinite Loops

    • visited matrix (or set) marks cells as visited the moment they are enqueued.
    • Before enqueuing a neighbor, we check not visited[r][c].
    • This ensures each cell is processed at most once, preventing cycles and redundant work.

    Path Reconstruction

    1. parent dictionary stores the predecessor of each visited cell:
      parent[(r, c)] = (prev_r, prev_c)  # We reached (r,c) from (prev_r, prev_c)
      
    2. When the target end is found, backtrack from end to start:
      current = end
      while current != start:
          path.append(current)
          current = parent[current]  # Move to predecessor
      path.append(start)
      path.reverse()  # To get start→end order
      
    3. This yields the actual sequence of cells in the shortest path.

    Example Usage

    grid = [
        [0, 0, 1, 0],
        [1, 0, 1, 0],
        [0, 0, 0, 0],
        [0, 1, 1, 0]
    ]
    start = (0, 0)
    end = (3, 3)
    
    path = shortest_path(grid, start, end)
    print(path)  
    # Output: [(0,0), (0,1), (1,1), (2,1), (2,2), (2,3), (3,3)]
    

    Complexity

    • Time: O(rows × cols) – each cell visited at most once.
    • Space: O(rows × cols) – for visited matrix, parent dict, and queue.

    Why Not Dijkstra or A?*

    • Dijkstra – Overkill for unweighted grids; BFS is simpler and equally efficient.
    • A* – Useful with heuristics for large grids, but requires an admissible heuristic (e.g., Manhattan distance). BFS is optimal for unweighted grids without extra overhead.

    BFS is the standard algorithm for unweighted shortest paths in grids.