name: Matrix Traversal
slug: matrix-traversal
difficulty_level: 3
pattern_type: algorithm
display_order: 9

description: >
  Navigate 2D grids systematically using DFS, BFS, or directional iteration.
  Matrix traversal combines graph traversal concepts with coordinate-based
  movement, treating each cell as a node connected to its neighbors.

when_to_use: |
  - Finding connected regions (islands)
  - Shortest path in a grid
  - Flood fill / painting
  - Spreading simulations (rotting oranges, fire spread)
  - Word search in character grid

metaphor: |
  Imagine being dropped into a maze viewed from above. You can move up, down,
  left, or right, but walls block certain paths. DFS is like exploring one
  corridor completely before backtracking. BFS is like sending scouts in all
  directions simultaneously—whoever reaches the exit first found the shortest path.

  Another analogy: painting a floor. Flood fill (DFS/BFS) starts at one point
  and spreads to all connected unpainted tiles.

core_concept: |
  A 2D grid is essentially a graph where each cell connects to its neighbors
  (4-directional or 8-directional). The key adaptations from graph traversal:

  1. **Nodes are coordinates**: Instead of node IDs, track `(row, col)` pairs
  2. **Edges are directions**: Neighbors are found by adding direction vectors
  3. **Bounds checking**: Validate coordinates before accessing the grid
  4. **In-place visited marking**: Often modify the grid itself instead of using
     a separate visited set (mark '1' → '0' to indicate visited)

  **When to use DFS vs BFS:**
  - **DFS**: Counting regions, checking if path exists, flood fill
  - **BFS**: Shortest path, simultaneous spreading from multiple sources

visualization: |
  **Example: Number of Islands**

  ```
  Grid (1 = land, 0 = water):

  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

  DFS from (0,0): marks all connected 1s as visited
  → Found island 1

  Continue scanning, DFS from (2,2):
  → Found island 2

  Continue scanning, DFS from (3,3):
  → Found island 3

  Answer: 3 islands
  ```

  **Shortest path in grid (BFS):**

  ```
  Grid (0 = passable, 1 = wall):

  0 0 0
  1 1 0
  0 0 0

  Start: (0,0)  End: (2,2)

  BFS levels:
  Level 0: (0,0)
  Level 1: (0,1)
  Level 2: (0,2)
  Level 3: (1,2)
  Level 4: (2,2) ← Found! Distance = 4
  ```

  **4-directional vs 8-directional:**

  ```
  4-directional:          8-directional:
      ↑                   ↖ ↑ ↗
    ← ○ →                 ← ○ →
      ↓                   ↙ ↓ ↘
  ```

code_template: |
  from collections import deque

  # Direction vectors
  DIRS_4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up
  DIRS_8 = [(0, 1), (0, -1), (1, 0), (-1, 0),
            (1, 1), (1, -1), (-1, 1), (-1, -1)]


  def is_valid(grid: list[list], row: int, col: int) -> bool:
      """Check if coordinates are within grid bounds."""
      return 0 <= row < len(grid) and 0 <= col < len(grid[0])


  def dfs_matrix(grid: list[list[int]], row: int, col: int) -> int:
      """DFS to explore connected region, returns size."""
      if not is_valid(grid, row, col) or grid[row][col] == 0:
          return 0

      grid[row][col] = 0  # Mark as visited (modify in-place)
      size = 1

      for dr, dc in DIRS_4:
          size += dfs_matrix(grid, row + dr, col + dc)

      return size


  def count_islands(grid: list[list[str]]) -> int:
      """Count connected regions of '1's."""
      if not grid:
          return 0

      count = 0
      rows, cols = len(grid), len(grid[0])

      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == '1':
                  count += 1
                  dfs_sink_island(grid, r, c)

      return count


  def dfs_sink_island(grid: list[list[str]], row: int, col: int):
      """Sink an island by marking all connected '1's as '0'."""
      if not is_valid(grid, row, col) or grid[row][col] == '0':
          return

      grid[row][col] = '0'  # Sink this cell

      for dr, dc in DIRS_4:
          dfs_sink_island(grid, row + dr, col + dc)


  def bfs_shortest_path(grid: list[list[int]],
                        start: tuple, end: tuple) -> int:
      """BFS to find shortest path in grid (0 = passable, 1 = wall)."""
      if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1:
          return -1

      rows, cols = len(grid), len(grid[0])
      queue = deque([(*start, 0)])  # (row, col, distance)
      visited = {start}

      while queue:
          row, col, dist = queue.popleft()

          if (row, col) == end:
              return dist

          for dr, dc in DIRS_4:
              nr, nc = row + dr, col + dc
              if (is_valid(grid, nr, nc)
                  and (nr, nc) not in visited
                  and grid[nr][nc] == 0):
                  visited.add((nr, nc))
                  queue.append((nr, nc, dist + 1))

      return -1  # No path


  def multi_source_bfs(grid: list[list[int]]) -> int:
      """BFS from multiple sources (e.g., rotting oranges)."""
      rows, cols = len(grid), len(grid[0])
      queue = deque()
      fresh = 0

      # Find all sources and count targets
      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == 2:  # Rotten orange
                  queue.append((r, c, 0))
              elif grid[r][c] == 1:  # Fresh orange
                  fresh += 1

      max_time = 0
      while queue:
          row, col, time = queue.popleft()
          max_time = max(max_time, time)

          for dr, dc in DIRS_4:
              nr, nc = row + dr, col + dc
              if is_valid(grid, nr, nc) and grid[nr][nc] == 1:
                  grid[nr][nc] = 2  # Mark as rotten
                  fresh -= 1
                  queue.append((nr, nc, time + 1))

      return max_time if fresh == 0 else -1

recognition_signals:
  - "grid"
  - "matrix"
  - "2D array"
  - "number of islands"
  - "shortest path in grid"
  - "flood fill"
  - "surrounded regions"
  - "rotting oranges"
  - "word search"
  - "robot path"
  - "maze"

common_mistakes:
  - title: Modifying grid while using it for bounds checking
    description: |
      If you use grid values for validity checks (like `grid[r][c] == '1'`)
      and also modify them in-place, you might check a cell you already modified.
    fix: |
      Modify the cell immediately upon visiting, before exploring neighbors:
      ```python
      grid[row][col] = '0'  # Mark first
      for dr, dc in DIRS_4:
          dfs(grid, row + dr, col + dc)  # Then explore
      ```

  - title: Forgetting to check all starting points
    description: |
      For problems like "number of islands," only starting DFS from (0,0) misses
      islands not connected to the top-left.
    fix: |
      Iterate through every cell and start a new traversal from each unvisited cell:
      ```python
      for r in range(rows):
          for c in range(cols):
              if grid[r][c] == '1':
                  count += 1
                  dfs(grid, r, c)
      ```

  - title: Index out of bounds
    description: |
      Accessing `grid[row][col]` without checking bounds first causes runtime
      errors when exploring neighbors.
    fix: |
      Always check bounds before accessing:
      ```python
      if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == target:
          # Safe to access
      ```

  - title: Using wrong direction set
    description: |
      Using 4-directional movement when problem requires 8-directional (diagonal)
      gives wrong results, or vice versa.
    fix: |
      Read the problem carefully. "Adjacent" usually means 4-directional.
      "Neighboring" or explicit diagonal mention means 8-directional.

variations:
  - name: Island counting
    description: |
      Count connected regions of the same value. DFS from each unvisited cell,
      marking the entire region as visited.
    example: "Number of Islands, Max Area of Island"

  - name: Shortest path in grid
    description: |
      BFS from start to end, counting levels. Works only if all moves have
      equal cost (unweighted).
    example: "Shortest Path in Binary Matrix, 01 Matrix"

  - name: Multi-source BFS
    description: |
      Start BFS from multiple cells simultaneously. Useful for spreading
      problems where multiple sources expand in parallel.
    example: "Rotting Oranges, Walls and Gates"

  - name: Word search
    description: |
      DFS with backtracking to find if a word exists in the grid by following
      adjacent cells. Need to track the current path to avoid reusing cells.
    example: "Word Search, Word Search II"

  - name: Spiral traversal
    description: |
      Not graph-based, but iterate through matrix in spiral order using
      boundary tracking (top, bottom, left, right).
    example: "Spiral Matrix, Spiral Matrix II"

related_patterns:
  - dfs
  - bfs
  - backtracking

prerequisite_patterns:
  - dfs
  - bfs
