Grid as Graph — Common Graph Modeling… | OneNoughtOne

0/97

Data Structures & AlgorithmsGraph Modeling Patterns

Common Graph Modeling Patterns

LevelIntermediate

Duration60 mins

TopicGraph Modeling Patterns

3 / 4

Grid as Graph

The Grid-Graph Connection

Grids are everywhere in computing—2D game worlds, image pixels, spreadsheets, maps, and mazes. At first glance, a grid seems like a simple 2D array. But there's a deeper structure hiding beneath: every grid is a graph . Once you see a grid as a graph, you unlock an entire toolkit of algorithms: BFS for shortest paths, DFS for exploration, Union-Find for connected regions, and more. This reframing transforms 'how do I navigate a maze?' into 'find the shortest path in a graph'—a solved problem.

What You Will Learn

By the end of this page, you will understand how to model any grid as a graph, implement graph algorithms on grids efficiently, and recognize grid-graph problems in interviews and real-world applications. You'll master the 4-directional and 8-directional movement patterns, handle obstacles, and solve classic problems like flood fill and shortest path in a maze.

Grid to Graph Mapping

The mapping from grid to graph is remarkably natural: Grid Cells \to Graph Vertices Each cell (row, col) in the grid becomes a vertex in the graph. A grid of size M \times N yields a graph with M \times N vertices. Cell Adjacency \to Graph Edges Two cells are connected by an edge if you can move directly between them. The definition of 'adjacent' depends on your problem: 4-directional (cardinal) : Up, down, left, right only 8-directional (including diagonals) : All 8 surrounding cells Custom : Knight moves in chess, hexagonal grids, etc. Cell Properties \to Vertex/Edge Properties Obstacle cells become either removed vertices or vertices with no outgoing edges Cell values can become vertex weights or edge weights Cell types (water, land, wall) determine edge existence

Grid-Graph Correspondence
Grid Concept	Graph Concept	Example
Cell (row, col)	Vertex	(2, 3) → vertex ID 2*cols + 3
Adjacent cells	Edge	(1,1)↔(1,2) for horizontal adjacency
Wall/obstacle	Missing vertex or no edges	Wall cells have no neighbors
Cell value	Vertex weight	Elevation for hiking cost
Movement cost	Edge weight	Terrain difficulty
Start position	Source vertex	Top-left corner
Target position	Destination vertex	Bottom-right corner

The Implicit Nature

Grid graphs are almost always implicit—you don't build an adjacency list for every cell. Instead, you compute neighbors on-the-fly using the direction arrays pattern. This is memory-efficient and often faster than explicit graph construction.

The Direction Arrays Pattern

The most elegant way to generate grid neighbors is the direction arrays pattern . Instead of writing separate logic for each direction, we use arrays of offsets: 4-directional: dx = [-1, 1, 0, 0] (row change) dy = [0, 0, -1, 1] (col change) 8-directional: dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] This pattern is so common that experienced engineers write it reflexively. Let's see it in action:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from typing import List, Tuple, Iterator
 
def get_4_neighbors(row: int, col: int, rows: int, cols: int) -> Iterator[Tuple[int, int]]:
    """
    Generate 4-directional neighbors (up, down, left, right).
    This is the implicit graph edge generation for grid problems.
    """
    # Direction arrays: [up, down, left, right]
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    for i in range(4):
        new_row = row + dr[i]
        new_col = col + dc[i]
        
        # Bounds checking (valid vertex in graph)
        if 0 <= new_row < rows and 0 <= new_col < cols:
            yield (new_row, new_col)
 
def get_8_neighbors(row: int, col: int, rows: int, cols: int) -> Iterator[Tuple[int, int]]:
    """
    Generate 8-directional neighbors (including diagonals).
    """
    for dr in [-1, 0, 1]:
        for dc in [-1, 0, 1]:
            if dr == 0 and dc == 0:
                continue  # Skip self
            
            new_row = row + dr
            new_col = col + dc
            
            if 0 <= new_row < rows and 0 <= new_col < cols:
                yield (new_row, new_col)
 
# Alternative: Using a single list of tuples (often cleaner)
DIRECTIONS_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
DIRECTIONS_8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
 
def get_neighbors(row: int, col: int, rows: int, cols: int, 
                  directions=DIRECTIONS_4) -> Iterator[Tuple[int, int]]:
    """
    Generic neighbor generator with customizable directions.
    """
    for dr, dc in directions:
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < rows and 0 <= new_col < cols:
            yield (new_row, new_col)

Why Direction Arrays?

Direction arrays avoid repetitive if-else chains and make the code extensible. Need knight moves? Just change the direction array. Need hexagonal grids? Different direction array. The neighbor generation logic stays the same.

BFS on Grids: Shortest Path in a Maze

The most common grid-graph problem is finding the shortest path from a start cell to a target cell, avoiding obstacles. Since each step has unit cost, BFS is optimal: The Problem: Given a grid where 0 = passable and 1 = wall, find the shortest path from top-left to bottom-right. Return the path length, or -1 if no path exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from collections import deque
from typing import List, Tuple, Optional
 
def shortest_path_grid(grid: List[List[int]]) -> int:
    """
    Find shortest path from (0,0) to (rows-1, cols-1) in a grid.
    0 = passable, 1 = wall.
    
    This is BFS on the implicit graph where:
    - Vertices: passable cells
    - Edges: 4-directional adjacency between passable cells
    
    Time Complexity: O(M × N) - each cell visited at most once
    Space Complexity: O(M × N) - for visited set and queue
    """
    if not grid or not grid[0]:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    
    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[rows-1][cols-1] == 1:
        return -1
    
    # Edge case: single cell grid
    if rows == 1 and cols == 1:
        return 1
    
    # Direction arrays for 4-directional movement
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS initialization
    queue = deque([(0, 0, 1)])  # (row, col, path_length)
    visited = {(0, 0)}
    
    while queue:
        row, col, distance = queue.popleft()
        
        # Explore neighbors (edges in the implicit graph)
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Bounds check (vertex exists in graph)
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Wall check (vertex is valid)
            if grid[new_row][new_col] == 1:
                continue
            
            # Already visited check
            if (new_row, new_col) in visited:
                continue
            
            # Goal check
            if new_row == rows - 1 and new_col == cols - 1:
                return distance + 1
            
            visited.add((new_row, new_col))
            queue.append((new_row, new_col, distance + 1))
    
    return -1  # No path exists
 
# Example usage
maze = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]
result = shortest_path_grid(maze)
print(f"Shortest path length: {result}")  # Output: 9

Key Points: We never build an adjacency list —neighbors are computed via direction arrays Visited set uses coordinate tuples —(row, col) uniquely identifies each vertex BFS guarantees shortest path —in unweighted graphs, first arrival is optimal Early termination —we return immediately upon reaching the goal This pattern is the foundation for countless grid problems: island counting, flood fill, rotting oranges, and more.

DFS on Grids: Flood Fill Algorithm

Flood fill—familiar from paint bucket tools in image editors—is a classic DFS application on grids: The Problem: Given an image (2D grid of colors), a starting pixel, and a new color, fill the connected region of the starting pixel's original color with the new color. This is graph traversal where we visit all vertices in a connected component.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from typing import List
 
def flood_fill(image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
    """
    Fill connected region starting from (sr, sc) with new_color.
    Uses DFS on the implicit grid graph.
    
    Vertices: pixels with the original color
    Edges: 4-directional adjacency between same-color pixels
    
    Time Complexity: O(M × N) - each pixel visited at most once
    Space Complexity: O(M × N) - recursion stack in worst case
    """
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]
    
    # Edge case: already the target color (avoid infinite recursion)
    if original_color == new_color:
        return image
    
    def dfs(row: int, col: int):
        """DFS to fill connected component."""
        # Bounds check
        if not (0 <= row < rows and 0 <= col < cols):
            return
        
        # Color check (only fill original color)
        if image[row][col] != original_color:
            return
        
        # Fill this pixel
        image[row][col] = new_color
        
        # Recursively fill 4-directional neighbors
        dfs(row - 1, col)  # Up
        dfs(row + 1, col)  # Down
        dfs(row, col - 1)  # Left
        dfs(row, col + 1)  # Right
    
    dfs(sr, sc)
    return image
 
# Example: Fill region starting from (1, 1)
image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
]
result = flood_fill(image, 1, 1, 2)
# Result: [[2,2,2],[2,2,0],[2,0,1]]

Recursion Depth Caution

For very large grids, recursive DFS can hit stack overflow limits. In production code, convert to iterative DFS with an explicit stack, or use BFS which has bounded queue size proportional to the grid perimeter.

Counting Islands (Connected Components)

Another classic grid problem: counting connected components. The Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. This is exactly the problem of counting connected components in a graph—each island is a component.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from typing import List
 
def num_islands(grid: List[List[str]]) -> int:
    """
    Count connected components of '1's in the grid.
    
    Approach: For each unvisited land cell, run DFS/BFS to mark
    all connected land cells as visited. Each DFS/BFS initiation
    discovers a new island.
    
    Time Complexity: O(M × N) - each cell visited at most once
    Space Complexity: O(M × N) - for visited set or recursion stack
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = set()
    island_count = 0
    
    def dfs(row: int, col: int):
        """Mark all cells in this island as visited."""
        # Bounds check
        if not (0 <= row < rows and 0 <= col < cols):
            return
        
        # Water or already visited
        if grid[row][col] == '0' or (row, col) in visited:
            return
        
        visited.add((row, col))
        
        # Explore all 4-directional neighbors
        dfs(row - 1, col)
        dfs(row + 1, col)
        dfs(row, col - 1)
        dfs(row, col + 1)
    
    # Scan through all cells
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1' and (row, col) not in visited:
                # Found a new island - explore it
                dfs(row, col)
                island_count += 1
    
    return island_count
 
# Example
grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(f"Number of islands: {num_islands(grid)}")  # Output: 3

Variations of This Pattern: Max Area of Island : Track size during DFS, return maximum Perimeter of Island : Count edges adjacent to water during DFS Making Islands Connect : BFS from multi-source to find minimum distance Surrounded Regions : Mark boundary-connected regions, flip others All these problems share the core insight: grid = graph, connected land = connected component.

Multi-Source BFS on Grids

A powerful grid technique is multi-source BFS —starting BFS from multiple sources simultaneously. This is useful when you need the distance from any of several starting points. Classic Problem: Rotting Oranges In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Each minute, rotten oranges rot adjacent fresh oranges. Return the minimum time for all oranges to rot, or -1 if impossible. Naive approach: BFS from each rotten orange separately. Better: Start BFS from all rotten oranges at once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from collections import deque
from typing import List
 
def oranges_rotting(grid: List[List[int]]) -> int:
    """
    Multi-source BFS from all rotten oranges simultaneously.
    
    Key insight: Instead of running BFS from each rotten orange,
    add ALL rotten oranges to the initial queue. BFS then spreads
    outward from all sources in lock-step.
    
    Time Complexity: O(M × N)
    Space Complexity: O(M × N)
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Initialize: add all rotten oranges to queue, count fresh
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                queue.append((row, col, 0))  # (row, col, time)
            elif grid[row][col] == 1:
                fresh_count += 1
    
    # Edge case: no fresh oranges to rot
    if fresh_count == 0:
        return 0
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    max_time = 0
    
    # BFS spreading from all rotten oranges
    while queue:
        row, col, time = queue.popleft()
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Only spread to fresh oranges
            if grid[new_row][new_col] == 1:
                grid[new_row][new_col] = 2  # Mark as rotten
                fresh_count -= 1
                max_time = max(max_time, time + 1)
                queue.append((new_row, new_col, time + 1))
    
    return max_time if fresh_count == 0 else -1
 
# Example
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
]
print(f"Time to rot all: {oranges_rotting(grid)}")  # Output: 4

Multi-Source BFS Applications

This pattern appears in many problems: 01 Matrix (distance to nearest 0), Walls and Gates (distance to nearest gate), Pacific Atlantic Water Flow (cells reachable from both oceans). The key is recognizing when you need minimum distance FROM a set of sources rather than TO a single destination.

Weighted Grid Graphs

Not all grid movements have equal cost. When cells have different traversal costs, we need Dijkstra's algorithm instead of BFS. Problem: Path with Minimum Effort Given a 2D grid of heights, find a path from top-left to bottom-right minimizing the maximum absolute height difference between consecutive cells. This is shortest path where 'distance' is the max edge weight on the path—classic Dijkstra application.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import heapq
from typing import List
 
def minimum_effort_path(heights: List[List[int]]) -> int:
    """
    Find path minimizing maximum height difference between adjacent cells.
    Uses Dijkstra's algorithm on the implicit grid graph.
    
    Edge weight: |heights[r1][c1] - heights[r2][c2]|
    Path cost: maximum edge weight on path
    Goal: minimize path cost
    
    Time Complexity: O(M × N × log(M × N))
    Space Complexity: O(M × N)
    """
    rows, cols = len(heights), len(heights[0])
    
    # dist[r][c] = minimum effort to reach (r, c)
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    
    # Priority queue: (effort, row, col)
    pq = [(0, 0, 0)]
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while pq:
        effort, row, col = heapq.heappop(pq)
        
        # Skip if we've found a better path to this cell
        if effort > dist[row][col]:
            continue
        
        # Goal check
        if row == rows - 1 and col == cols - 1:
            return effort
        
        # Explore neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Edge weight = height difference
            edge_weight = abs(heights[row][col] - heights[new_row][new_col])
            
            # Path cost = max of current effort and this edge
            new_effort = max(effort, edge_weight)
            
            if new_effort < dist[new_row][new_col]:
                dist[new_row][new_col] = new_effort
                heapq.heappush(pq, (new_effort, new_row, new_col))
    
    return dist[rows-1][cols-1]
 
# Example
heights = [
    [1, 2, 2],
    [3, 8, 2],
    [5, 3, 5]
]
print(f"Minimum effort: {minimum_effort_path(heights)}")  # Output: 2

When to Use Which Algorithm on Grids:

Scenario	Algorithm	Time Complexity
Unweighted grid, shortest path	BFS	O(M × N)
Weighted grid, shortest path	Dijkstra	O(M × N × log(M×N))
All same-weight edges	BFS	O(M × N)
0-1 edge weights	0-1 BFS with deque	O(M × N)
Negative weights	Bellman-Ford	O(M × N × (M + N))
Count reachable cells	DFS/BFS	O(M × N)

Data Structures & AlgorithmsGraph Modeling Patterns

Common Graph Modeling Patterns

LevelIntermediate

Duration60 mins

TopicGraph Modeling Patterns

3 / 4

Grid as Graph

The Grid-Graph Connection

Grids are everywhere in computing—2D game worlds, image pixels, spreadsheets, maps, and mazes. At first glance, a grid seems like a simple 2D array. But there's a deeper structure hiding beneath: every grid is a graph . Once you see a grid as a graph, you unlock an entire toolkit of algorithms: BFS for shortest paths, DFS for exploration, Union-Find for connected regions, and more. This reframing transforms 'how do I navigate a maze?' into 'find the shortest path in a graph'—a solved problem.

What You Will Learn

By the end of this page, you will understand how to model any grid as a graph, implement graph algorithms on grids efficiently, and recognize grid-graph problems in interviews and real-world applications. You'll master the 4-directional and 8-directional movement patterns, handle obstacles, and solve classic problems like flood fill and shortest path in a maze.

Grid to Graph Mapping

The mapping from grid to graph is remarkably natural: Grid Cells \to Graph Vertices Each cell (row, col) in the grid becomes a vertex in the graph. A grid of size M \times N yields a graph with M \times N vertices. Cell Adjacency \to Graph Edges Two cells are connected by an edge if you can move directly between them. The definition of 'adjacent' depends on your problem: 4-directional (cardinal) : Up, down, left, right only 8-directional (including diagonals) : All 8 surrounding cells Custom : Knight moves in chess, hexagonal grids, etc. Cell Properties \to Vertex/Edge Properties Obstacle cells become either removed vertices or vertices with no outgoing edges Cell values can become vertex weights or edge weights Cell types (water, land, wall) determine edge existence

Grid-Graph Correspondence
Grid Concept	Graph Concept	Example
Cell (row, col)	Vertex	(2, 3) → vertex ID 2*cols + 3
Adjacent cells	Edge	(1,1)↔(1,2) for horizontal adjacency
Wall/obstacle	Missing vertex or no edges	Wall cells have no neighbors
Cell value	Vertex weight	Elevation for hiking cost
Movement cost	Edge weight	Terrain difficulty
Start position	Source vertex	Top-left corner
Target position	Destination vertex	Bottom-right corner

The Implicit Nature

Grid graphs are almost always implicit—you don't build an adjacency list for every cell. Instead, you compute neighbors on-the-fly using the direction arrays pattern. This is memory-efficient and often faster than explicit graph construction.

The Direction Arrays Pattern

The most elegant way to generate grid neighbors is the direction arrays pattern . Instead of writing separate logic for each direction, we use arrays of offsets: 4-directional: dx = [-1, 1, 0, 0] (row change) dy = [0, 0, -1, 1] (col change) 8-directional: dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] This pattern is so common that experienced engineers write it reflexively. Let's see it in action:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from typing import List, Tuple, Iterator
 
def get_4_neighbors(row: int, col: int, rows: int, cols: int) -> Iterator[Tuple[int, int]]:
    """
    Generate 4-directional neighbors (up, down, left, right).
    This is the implicit graph edge generation for grid problems.
    """
    # Direction arrays: [up, down, left, right]
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    for i in range(4):
        new_row = row + dr[i]
        new_col = col + dc[i]
        
        # Bounds checking (valid vertex in graph)
        if 0 <= new_row < rows and 0 <= new_col < cols:
            yield (new_row, new_col)
 
def get_8_neighbors(row: int, col: int, rows: int, cols: int) -> Iterator[Tuple[int, int]]:
    """
    Generate 8-directional neighbors (including diagonals).
    """
    for dr in [-1, 0, 1]:
        for dc in [-1, 0, 1]:
            if dr == 0 and dc == 0:
                continue  # Skip self
            
            new_row = row + dr
            new_col = col + dc
            
            if 0 <= new_row < rows and 0 <= new_col < cols:
                yield (new_row, new_col)
 
# Alternative: Using a single list of tuples (often cleaner)
DIRECTIONS_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
DIRECTIONS_8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
 
def get_neighbors(row: int, col: int, rows: int, cols: int, 
                  directions=DIRECTIONS_4) -> Iterator[Tuple[int, int]]:
    """
    Generic neighbor generator with customizable directions.
    """
    for dr, dc in directions:
        new_row, new_col = row + dr, col + dc
        if 0 <= new_row < rows and 0 <= new_col < cols:
            yield (new_row, new_col)

Why Direction Arrays?

Direction arrays avoid repetitive if-else chains and make the code extensible. Need knight moves? Just change the direction array. Need hexagonal grids? Different direction array. The neighbor generation logic stays the same.

BFS on Grids: Shortest Path in a Maze

The most common grid-graph problem is finding the shortest path from a start cell to a target cell, avoiding obstacles. Since each step has unit cost, BFS is optimal: The Problem: Given a grid where 0 = passable and 1 = wall, find the shortest path from top-left to bottom-right. Return the path length, or -1 if no path exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from collections import deque
from typing import List, Tuple, Optional
 
def shortest_path_grid(grid: List[List[int]]) -> int:
    """
    Find shortest path from (0,0) to (rows-1, cols-1) in a grid.
    0 = passable, 1 = wall.
    
    This is BFS on the implicit graph where:
    - Vertices: passable cells
    - Edges: 4-directional adjacency between passable cells
    
    Time Complexity: O(M × N) - each cell visited at most once
    Space Complexity: O(M × N) - for visited set and queue
    """
    if not grid or not grid[0]:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    
    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[rows-1][cols-1] == 1:
        return -1
    
    # Edge case: single cell grid
    if rows == 1 and cols == 1:
        return 1
    
    # Direction arrays for 4-directional movement
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS initialization
    queue = deque([(0, 0, 1)])  # (row, col, path_length)
    visited = {(0, 0)}
    
    while queue:
        row, col, distance = queue.popleft()
        
        # Explore neighbors (edges in the implicit graph)
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Bounds check (vertex exists in graph)
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Wall check (vertex is valid)
            if grid[new_row][new_col] == 1:
                continue
            
            # Already visited check
            if (new_row, new_col) in visited:
                continue
            
            # Goal check
            if new_row == rows - 1 and new_col == cols - 1:
                return distance + 1
            
            visited.add((new_row, new_col))
            queue.append((new_row, new_col, distance + 1))
    
    return -1  # No path exists
 
# Example usage
maze = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]
result = shortest_path_grid(maze)
print(f"Shortest path length: {result}")  # Output: 9

Key Points: We never build an adjacency list —neighbors are computed via direction arrays Visited set uses coordinate tuples —(row, col) uniquely identifies each vertex BFS guarantees shortest path —in unweighted graphs, first arrival is optimal Early termination —we return immediately upon reaching the goal This pattern is the foundation for countless grid problems: island counting, flood fill, rotting oranges, and more.

DFS on Grids: Flood Fill Algorithm

Flood fill—familiar from paint bucket tools in image editors—is a classic DFS application on grids: The Problem: Given an image (2D grid of colors), a starting pixel, and a new color, fill the connected region of the starting pixel's original color with the new color. This is graph traversal where we visit all vertices in a connected component.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from typing import List
 
def flood_fill(image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
    """
    Fill connected region starting from (sr, sc) with new_color.
    Uses DFS on the implicit grid graph.
    
    Vertices: pixels with the original color
    Edges: 4-directional adjacency between same-color pixels
    
    Time Complexity: O(M × N) - each pixel visited at most once
    Space Complexity: O(M × N) - recursion stack in worst case
    """
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]
    
    # Edge case: already the target color (avoid infinite recursion)
    if original_color == new_color:
        return image
    
    def dfs(row: int, col: int):
        """DFS to fill connected component."""
        # Bounds check
        if not (0 <= row < rows and 0 <= col < cols):
            return
        
        # Color check (only fill original color)
        if image[row][col] != original_color:
            return
        
        # Fill this pixel
        image[row][col] = new_color
        
        # Recursively fill 4-directional neighbors
        dfs(row - 1, col)  # Up
        dfs(row + 1, col)  # Down
        dfs(row, col - 1)  # Left
        dfs(row, col + 1)  # Right
    
    dfs(sr, sc)
    return image
 
# Example: Fill region starting from (1, 1)
image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
]
result = flood_fill(image, 1, 1, 2)
# Result: [[2,2,2],[2,2,0],[2,0,1]]

Recursion Depth Caution

For very large grids, recursive DFS can hit stack overflow limits. In production code, convert to iterative DFS with an explicit stack, or use BFS which has bounded queue size proportional to the grid perimeter.

Counting Islands (Connected Components)

Another classic grid problem: counting connected components. The Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. This is exactly the problem of counting connected components in a graph—each island is a component.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from typing import List
 
def num_islands(grid: List[List[str]]) -> int:
    """
    Count connected components of '1's in the grid.
    
    Approach: For each unvisited land cell, run DFS/BFS to mark
    all connected land cells as visited. Each DFS/BFS initiation
    discovers a new island.
    
    Time Complexity: O(M × N) - each cell visited at most once
    Space Complexity: O(M × N) - for visited set or recursion stack
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = set()
    island_count = 0
    
    def dfs(row: int, col: int):
        """Mark all cells in this island as visited."""
        # Bounds check
        if not (0 <= row < rows and 0 <= col < cols):
            return
        
        # Water or already visited
        if grid[row][col] == '0' or (row, col) in visited:
            return
        
        visited.add((row, col))
        
        # Explore all 4-directional neighbors
        dfs(row - 1, col)
        dfs(row + 1, col)
        dfs(row, col - 1)
        dfs(row, col + 1)
    
    # Scan through all cells
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1' and (row, col) not in visited:
                # Found a new island - explore it
                dfs(row, col)
                island_count += 1
    
    return island_count
 
# Example
grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(f"Number of islands: {num_islands(grid)}")  # Output: 3

Variations of This Pattern: Max Area of Island : Track size during DFS, return maximum Perimeter of Island : Count edges adjacent to water during DFS Making Islands Connect : BFS from multi-source to find minimum distance Surrounded Regions : Mark boundary-connected regions, flip others All these problems share the core insight: grid = graph, connected land = connected component.

Multi-Source BFS on Grids

A powerful grid technique is multi-source BFS —starting BFS from multiple sources simultaneously. This is useful when you need the distance from any of several starting points. Classic Problem: Rotting Oranges In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Each minute, rotten oranges rot adjacent fresh oranges. Return the minimum time for all oranges to rot, or -1 if impossible. Naive approach: BFS from each rotten orange separately. Better: Start BFS from all rotten oranges at once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from collections import deque
from typing import List
 
def oranges_rotting(grid: List[List[int]]) -> int:
    """
    Multi-source BFS from all rotten oranges simultaneously.
    
    Key insight: Instead of running BFS from each rotten orange,
    add ALL rotten oranges to the initial queue. BFS then spreads
    outward from all sources in lock-step.
    
    Time Complexity: O(M × N)
    Space Complexity: O(M × N)
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Initialize: add all rotten oranges to queue, count fresh
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                queue.append((row, col, 0))  # (row, col, time)
            elif grid[row][col] == 1:
                fresh_count += 1
    
    # Edge case: no fresh oranges to rot
    if fresh_count == 0:
        return 0
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    max_time = 0
    
    # BFS spreading from all rotten oranges
    while queue:
        row, col, time = queue.popleft()
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Only spread to fresh oranges
            if grid[new_row][new_col] == 1:
                grid[new_row][new_col] = 2  # Mark as rotten
                fresh_count -= 1
                max_time = max(max_time, time + 1)
                queue.append((new_row, new_col, time + 1))
    
    return max_time if fresh_count == 0 else -1
 
# Example
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
]
print(f"Time to rot all: {oranges_rotting(grid)}")  # Output: 4

Multi-Source BFS Applications

This pattern appears in many problems: 01 Matrix (distance to nearest 0), Walls and Gates (distance to nearest gate), Pacific Atlantic Water Flow (cells reachable from both oceans). The key is recognizing when you need minimum distance FROM a set of sources rather than TO a single destination.

Weighted Grid Graphs

Not all grid movements have equal cost. When cells have different traversal costs, we need Dijkstra's algorithm instead of BFS. Problem: Path with Minimum Effort Given a 2D grid of heights, find a path from top-left to bottom-right minimizing the maximum absolute height difference between consecutive cells. This is shortest path where 'distance' is the max edge weight on the path—classic Dijkstra application.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import heapq
from typing import List
 
def minimum_effort_path(heights: List[List[int]]) -> int:
    """
    Find path minimizing maximum height difference between adjacent cells.
    Uses Dijkstra's algorithm on the implicit grid graph.
    
    Edge weight: |heights[r1][c1] - heights[r2][c2]|
    Path cost: maximum edge weight on path
    Goal: minimize path cost
    
    Time Complexity: O(M × N × log(M × N))
    Space Complexity: O(M × N)
    """
    rows, cols = len(heights), len(heights[0])
    
    # dist[r][c] = minimum effort to reach (r, c)
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    
    # Priority queue: (effort, row, col)
    pq = [(0, 0, 0)]
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while pq:
        effort, row, col = heapq.heappop(pq)
        
        # Skip if we've found a better path to this cell
        if effort > dist[row][col]:
            continue
        
        # Goal check
        if row == rows - 1 and col == cols - 1:
            return effort
        
        # Explore neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if not (0 <= new_row < rows and 0 <= new_col < cols):
                continue
            
            # Edge weight = height difference
            edge_weight = abs(heights[row][col] - heights[new_row][new_col])
            
            # Path cost = max of current effort and this edge
            new_effort = max(effort, edge_weight)
            
            if new_effort < dist[new_row][new_col]:
                dist[new_row][new_col] = new_effort
                heapq.heappush(pq, (new_effort, new_row, new_col))
    
    return dist[rows-1][cols-1]
 
# Example
heights = [
    [1, 2, 2],
    [3, 8, 2],
    [5, 3, 5]
]
print(f"Minimum effort: {minimum_effort_path(heights)}")  # Output: 2

When to Use Which Algorithm on Grids:

Scenario	Algorithm	Time Complexity
Unweighted grid, shortest path	BFS	O(M × N)
Weighted grid, shortest path	Dijkstra	O(M × N × log(M×N))
All same-weight edges	BFS	O(M × N)
0-1 edge weights	0-1 BFS with deque	O(M × N)
Negative weights	Bellman-Ford	O(M × N × (M + N))
Count reachable cells	DFS/BFS	O(M × N)

Grid as Graph

The Grid-Graph Connection

Grid to Graph Mapping

The Direction Arrays Pattern

BFS on Grids: Shortest Path in a Maze

DFS on Grids: Flood Fill Algorithm

Counting Islands (Connected Components)

Multi-Source BFS on Grids

Weighted Grid Graphs

There’s more to understand.

Grid as Graph

The Grid-Graph Connection

Grid to Graph Mapping

The Direction Arrays Pattern

BFS on Grids: Shortest Path in a Maze

DFS on Grids: Flood Fill Algorithm

Counting Islands (Connected Components)

Multi-Source BFS on Grids

Weighted Grid Graphs

There’s more to understand.