# LeetCode 130: Surrounded Regions — Step-by-Step Visual Trace

**Medium** — Depth-First Search | Matrix | Graph Traversal | Flood Fill

## The Problem

Given a 2D board containing 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' by flipping them to 'X'. Regions connected to the border cannot be captured.

## Approach

Use DFS to mark all 'O' cells connected to the border as 'E' (escaped). Then traverse the entire board: flip remaining 'O' cells to 'X' (captured) and restore 'E' cells back to 'O' (escaped). This reverse approach identifies uncapturable regions first.

**Time:** O(m×n) · **Space:** O(m×n)

## Code

```python
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        

        def dfs(row, col):
            if (
                row < 0
                or row >= len(board)
                or col < 0
                or col >= len(board[0])
                or board[row][col] != "O"
            ):
                return

            board[row][col] = "E"  # Mark as visited but not surrounded

            # Check adjacent cells
            dfs(row + 1, col)  # Check down
            dfs(row - 1, col)  # Check up
            dfs(row, col + 1)  # Check right
            dfs(row, col - 1)  # Check left

        # Traverse the boundary and mark connected 'O' cells as 'E'
        for row in range(len(board)):
            if board[row][0] == "O":
                dfs(row, 0)
            if board[row][len(board[0]) - 1] == "O":
                dfs(row, len(board[0]) - 1)

        for col in range(len(board[0])):
            if board[0][col] == "O":
                dfs(0, col)
            if board[len(board) - 1][col] == "O":
                dfs(len(board) - 1, col)

        # Mark internal 'O' cells as 'X' and restore 'E' cells to 'O'
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == "O":
                    board[row][col] = "X"
                elif board[row][col] == "E":
                    board[row][col] = "O"
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0130_surrounded-regions)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0130_surrounded-regions) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*