# LeetCode 130: Surrounded Regions

## Problem Restatement

We are given an `m x n` board containing only two characters:

| Character | Meaning |
|---|---|
| `"X"` | Wall or blocking cell |
| `"O"` | Open cell |

We need to capture every region of `"O"` cells that is completely surrounded by `"X"` cells.

A region is connected 4-directionally, meaning cells connect through up, down, left, and right. Diagonal connection does not count.

To capture a surrounded region, we flip every `"O"` in that region into `"X"`.

The modification must happen in-place. The function does not return a new board. LeetCode states that surrounded regions are captured by replacing all surrounded `"O"` cells with `"X"` in the original board.

## Examples

Example 1:

```python
board = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"],
]
```

The middle `"O"` cells are surrounded:

```text
(1, 1), (1, 2), (2, 2)
```

They do not touch the border, and they have no path to a border `"O"`.

The bottom `"O"` at `(3, 1)` is on the border, so it cannot be captured.

After solving:

```python
[
    ["X", "X", "X", "X"],
    ["X", "X", "X", "X"],
    ["X", "X", "X", "X"],
    ["X", "O", "X", "X"],
]
```

Example 2:

```python
board = [["X"]]
```

There is no `"O"` region to capture.

Output:

```python
[["X"]]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `board: list[list[str]]` |
| Output | Nothing, modify `board` in-place |
| Cell values | `"X"` or `"O"` |
| Connection | 4-directional only |
| Captured region | An `"O"` component with no connection to the border |

Function shape:

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

## First Thought: Check Each O Region

One direct idea is:

1. Find an unvisited `"O"`.
2. Explore its whole connected region.
3. Decide whether the region touches the border.
4. If it does not touch the border, flip the region to `"X"`.

This works, but the bookkeeping is heavier because each region must store its cells until we know whether it is captured.

There is a simpler reverse view.

## Key Insight

Instead of finding surrounded regions directly, find the regions that cannot be captured.

An `"O"` cannot be captured if it is connected to the border.

That includes:

1. Every `"O"` on the border.
2. Every `"O"` connected to a border `"O"` through other `"O"` cells.

So we mark all border-connected `"O"` cells as safe.

Then every remaining `"O"` must be surrounded.

Use a temporary marker, for example `"#"`:

| Cell after marking | Meaning |
|---|---|
| `"#"` | This was an `"O"` connected to the border, so keep it |
| `"O"` | This `"O"` was not connected to the border, so flip it |
| `"X"` | Already blocked |

## Why Border Search Works

A captured region is completely surrounded by `"X"`.

That means it has no path to any border cell.

So the only `"O"` cells that survive are exactly the cells reachable from the border.

This reverses the problem:

Instead of asking:

```text
Which O regions are surrounded?
```

ask:

```text
Which O cells can escape to the border?
```

The second question is easier because the starting cells are only on the border.

## Algorithm

Let `m` be the number of rows and `n` be the number of columns.

1. Scan the border cells.
2. Whenever a border cell is `"O"`, run DFS from it.
3. The DFS changes every reachable `"O"` into `"#"`.
4. After marking, scan the whole board:
   - Change remaining `"O"` to `"X"`.
   - Change `"#"` back to `"O"`.

The board is modified in-place.

## Correctness

A cell marked `"#"` was reached by DFS starting from a border `"O"`. Therefore, it is connected to the border through `"O"` cells. Such a cell cannot be part of a surrounded region, so changing it back to `"O"` is correct.

Any `"O"` left unmarked after the border DFS has no path to the border. If it had such a path, the DFS from that border-connected component would have reached it and marked it. Therefore, this remaining `"O"` belongs to a region fully enclosed away from the border, so flipping it to `"X"` is correct.

Every cell is either border-connected and preserved, or not border-connected and captured. Therefore, the algorithm produces exactly the required board.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `m` | Number of rows |
| `n` | Number of columns |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | Each cell is processed a constant number of times |
| Space | `O(m * n)` | DFS recursion stack can hold many cells in the worst case |

The board itself is modified in-place.

## Implementation

```python
class Solution:
    def solve(self, board: list[list[str]]) -> None:
        m = len(board)
        n = len(board[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= m or c < 0 or c >= n:
                return

            if board[r][c] != "O":
                return

            board[r][c] = "#"

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(m):
            dfs(r, 0)
            dfs(r, n - 1)

        for c in range(n):
            dfs(0, c)
            dfs(m - 1, c)

        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "#":
                    board[r][c] = "O"
```

## Code Explanation

We first get the board dimensions:

```python
m = len(board)
n = len(board[0])
```

The helper function marks all `"O"` cells connected to a starting cell:

```python
def dfs(r: int, c: int) -> None:
```

If the position is outside the board, stop:

```python
if r < 0 or r >= m or c < 0 or c >= n:
    return
```

If the cell is not `"O"`, stop:

```python
if board[r][c] != "O":
    return
```

Otherwise, mark it safe:

```python
board[r][c] = "#"
```

Then visit its four neighbors:

```python
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
```

Next, we start DFS from the left and right borders:

```python
for r in range(m):
    dfs(r, 0)
    dfs(r, n - 1)
```

Then from the top and bottom borders:

```python
for c in range(n):
    dfs(0, c)
    dfs(m - 1, c)
```

Finally, we scan every cell:

```python
if board[r][c] == "O":
    board[r][c] = "X"
elif board[r][c] == "#":
    board[r][c] = "O"
```

Remaining `"O"` cells are captured. Safe cells are restored.

## Iterative BFS Version

Recursive DFS is clear, but Python recursion can be risky for a large `200 x 200` board.

An iterative BFS avoids recursion depth issues.

```python
from collections import deque

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        m = len(board)
        n = len(board[0])
        queue = deque()

        def add_if_border_o(r: int, c: int) -> None:
            if board[r][c] == "O":
                board[r][c] = "#"
                queue.append((r, c))

        for r in range(m):
            add_if_border_o(r, 0)
            add_if_border_o(r, n - 1)

        for c in range(n):
            add_if_border_o(0, c)
            add_if_border_o(m - 1, c)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue

                if board[nr][nc] != "O":
                    continue

                board[nr][nc] = "#"
                queue.append((nr, nc))

        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "#":
                    board[r][c] = "O"
```

For LeetCode, I would submit the BFS version in Python because it avoids recursion depth problems.

## Testing

```python
def run_tests():
    s = Solution()

    board = [
        ["X", "X", "X", "X"],
        ["X", "O", "O", "X"],
        ["X", "X", "O", "X"],
        ["X", "O", "X", "X"],
    ]
    s.solve(board)
    assert board == [
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"],
    ]

    board = [["X"]]
    s.solve(board)
    assert board == [["X"]]

    board = [["O"]]
    s.solve(board)
    assert board == [["O"]]

    board = [
        ["O", "O"],
        ["O", "O"],
    ]
    s.solve(board)
    assert board == [
        ["O", "O"],
        ["O", "O"],
    ]

    board = [
        ["X", "X", "X"],
        ["X", "O", "X"],
        ["X", "X", "X"],
    ]
    s.solve(board)
    assert board == [
        ["X", "X", "X"],
        ["X", "X", "X"],
        ["X", "X", "X"],
    ]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Captures only the enclosed region |
| Single `"X"` | No change |
| Single `"O"` | Border cell cannot be captured |
| All `"O"` board | Every cell is border-connected |
| Center `"O"` surrounded by `"X"` | Smallest captured region |