Loading learning content...
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.
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.
The mapping from grid to graph is remarkably natural:
Grid Cells → Graph Vertices
Each cell (row, col) in the grid becomes a vertex in the graph. A grid of size M × N yields a graph with M × N vertices.
Cell Adjacency → Graph Edges
Two cells are connected by an edge if you can move directly between them. The definition of 'adjacent' depends on your problem:
Cell Properties → Vertex/Edge Properties
| 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 |
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 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:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
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)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.
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.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
from collections import dequefrom 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 usagemaze = [ [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: 9Key Points:
This pattern is the foundation for countless grid problems: island counting, flood fill, rotting oranges, and more.
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.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
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]]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.
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.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
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 # Examplegrid = [ ["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: 3Variations of This Pattern:
All these problems share the core insight: grid = graph, connected land = connected component.
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.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
from collections import dequefrom 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 # Examplegrid = [ [2, 1, 1], [1, 1, 0], [0, 1, 1]]print(f"Time to rot all: {oranges_rotting(grid)}") # Output: 4This 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.
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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
import heapqfrom 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] # Exampleheights = [ [1, 2, 2], [3, 8, 2], [5, 3, 5]]print(f"Minimum effort: {minimum_effort_path(heights)}") # Output: 2When 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) |
Let's catalog the patterns you'll encounter repeatedly in grid-graph problems:
| Problem | Pattern | Key Insight |
|---|---|---|
| Number of Islands | Connected Components | Each DFS explores one island |
| Surrounded Regions | Boundary DFS | Mark boundary-connected, flip rest |
| Rotting Oranges | Multi-Source BFS | Start from all rotten simultaneously |
| 01 Matrix | Multi-Source BFS | Start from all 0s, propagate distance |
| Shortest Path in Binary Matrix | BFS | 8-directional movement variation |
| Walls and Gates | Multi-Source BFS | Start from all gates |
| Pacific Atlantic Water Flow | Boundary DFS | DFS from each ocean inward |
| Shortest Bridge | DFS + BFS | DFS to find island, BFS to expand |
The grid-as-graph model is one of the most practical graph modeling patterns. Master it, and a huge category of problems becomes approachable.
What's Next:
The final page of this module explores modeling dependencies and constraints—representing prerequisite relationships, scheduling constraints, and other dependency structures as directed graphs for topological sorting and feasibility analysis.
You now understand how to model grids as implicit graphs and apply graph algorithms to solve maze navigation, flood fill, island counting, and shortest path problems. This pattern appears constantly in interviews and real-world applications—from game development to image processing to robot navigation.