Full lesson preview

Find the shortest path in an unweighted grid using BFS

Compute the minimum number of moves from start to end in a 2D grid with obstacles using BFS.

Python practice30 minStacks & QueuesAdvancedLast updated March 27, 2026

Problem statement

You are given a 2D grid represented as a list of lists of integers. 0 represents a walkable cell and 1 represents an obstacle. Given a start coordinate and an end coordinate (each a tuple of row and column), return the minimum number of moves required to reach the end from the start. Moves are allowed only in the four cardinal directions (up, down, left, right) and you cannot move through obstacles or outside the grid. If the end is unreachable, return -1. Notes: - The grid may be rectangular. Rows are indexed 0..m-1 and columns 0..n-1. - The start or end may be the same cell. - The start or end can be an obstacle; if so, the result is -1 unless start == end and that cell is walkable. Implement shortest_path(grid, start, end) to return the minimum number of moves or -1 if unreachable.

Task

Implement a breadth-first search (BFS) to find the shortest path length in an unweighted 2D grid, handling obstacles and edge cases.

Examples

Simple open grid

Input

shortest_path([[0,0],[0,0]], (0,0), (1,1))

Output

From (0,0) to (1,1) you need two moves: right+down or down+right.

Input format

A list of lists 'grid' where grid[r][c] is 0 (free) or 1 (obstacle), and two tuples 'start' and 'end' as (row, col).

Output format

An integer: the minimum number of moves as an int, or -1 if unreachable.

Constraints

0 <= rows, cols <= 200. Time complexity expected O(rows * cols). Use BFS to guarantee shortest path in an unweighted grid.

Samples

Sample 1

Input

shortest_path([[0,0,0],[1,1,0],[0,0,0]], (0,0), (2,2))

Output

A path exists around the blocked cells: (0,0)->(0,1)->(0,2)->(1,2)->(2,2) with 4 moves.