BFS on grid

Question

Implement a Breadth-First Search (BFS) algorithm to traverse a 2D grid, where each cell can either be passable or blocked. Given the starting and ending coordinates, determine the shortest path from the start to the end cell, returning the path length or -1 if no path exists. The grid is represented as a matrix of 0s (passable) and 1s (blocked).

Codemia · Accepted Answer

This problem involves finding the shortest path in a 2D grid using the Breadth-First Search (BFS) algorithm. BFS is particularly suited for this problem because it explores all neighbors at the present depth prior to moving on to nodes at the next depth level, ensuring that we find the shortest path in an unweighted grid. The grid is represented as a matrix of 0s (passable) and 1s (blocked), and the goal is to determine the shortest path from a starting coordinate to an ending coordinate. BFS will allow us to systematically explore all possible paths from the start to the end, layer by layer.

1. **Initialize**: Create a queue to hold the current position and a set to track visited cells. Start by enqueueing the starting coordinates. Initialize the path length as 0.

2. **BFS Loop**: While the queue is not empty, do the following:
   - Increment the path length by 1.
   - For each cell in the queue, explore its neighbors (up, down, left, right).
   - For each neighbor, check if it is within bounds, passable (0), and not yet visited. If it is the ending coordinate, return the path length.
   - If it's valid, mark it as visited and enqueue it.

3. **End Condition**: If the queue is exhausted and the end cell hasn't been reached, return -1, indicating that no path exists.

**Example**: For a grid like this:
```
0 0 1 0
0 0 0 0
1 1 0 1
0 0 0 0
```
Starting at (0,0) and ending at (3,3), the BFS will explore paths layer by layer until it finds the shortest one.

Here is a Python implementation of the BFS algorithm for this problem:
```python
from collections import deque

def bfs_shortest_path(grid, start, end):
    if not grid or not grid[0]:
        return -1
    rows, cols = len(grid), len(grid[0])
    queue = deque([start])
    visited = set([start])
    path_length = 0
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up

while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            if (x, y) == end:
                return path_length
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0 and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
        path_length += 1
    return -1
```
This code initializes BFS, processes the grid, and returns the shortest path length or -1 if the path does not exist.

The time complexity of this BFS solution is O(N * M), where N is the number of rows and M is the number of columns in the grid. This is because, in the worst case, we may have to explore each cell of the grid once. The space complexity is also O(N * M) due to the storage requirements for the queue and the visited set, which may both grow to the size of the grid in the worst case.

1. **Start or End Blocked**: If the starting or ending cell is blocked (1), return -1 immediately.
2. **Single Cell Grid**: If the grid is 1x1 and that cell is passable (0), return 0, as we are already at the destination.
3. **Disconnected Sections**: If the start and end are in disconnected sections of the grid, ensure the algorithm correctly returns -1. 
4. **All Cells Blocked**: If the grid is entirely blocked, the algorithm should also return -1.

BFS on grid

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string