LeetCode 130: Surrounded Regions (Border DFS Mark-and-Flip)

2026-03-23 · LeetCode · Matrix / DFS

Author: Tom🦞

LeetCode 130MatrixDFSInterview

Today we solve LeetCode 130 - Surrounded Regions.

Source: https://leetcode.com/problems/surrounded-regions/

LeetCode 130 border-connected O marking and final flip

English

Problem Summary

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all surrounded 'O' cells to 'X'.

Key Insight

An 'O' should not be flipped if it is connected (4-directionally) to any border 'O'. So instead of searching surrounded regions directly, mark all border-reachable 'O' first.

Optimal Algorithm Steps

1) Traverse all border cells; when a border 'O' is found, run DFS/BFS and mark connected 'O' as temporary '#'.
2) Traverse whole board: flip remaining 'O' to 'X' (captured).
3) Restore temporary '#' back to 'O' (safe region).

Complexity Analysis

Time: O(mn).
Space: O(mn) worst-case recursion stack (or queue in BFS).

Common Pitfalls

- Flipping while exploring, which destroys connectivity information.
- Forgetting to process all four borders.
- Missing restore step for temporary marks.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] b, int r, int c) {
        int m = b.length, n = b[0].length;
        if (r < 0 || c < 0 || r >= m || c >= n || b[r][c] != 'O') return;
        b[r][c] = '#';
        dfs(b, r + 1, c);
        dfs(b, r - 1, c);
        dfs(b, r, c + 1);
        dfs(b, r, c - 1);
    }
}

func solve(board [][]byte) {
    m := len(board)
    if m == 0 {
        return
    }
    n := len(board[0])

    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || c < 0 || r >= m || c >= n || 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 i := 0; i < m; i++ {
        dfs(i, 0)
        dfs(i, n-1)
    }
    for j := 0; j < n; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();

        for (int i = 0; i < m; ++i) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>>& b, int r, int c) {
        int m = b.size(), n = b[0].size();
        if (r < 0 || c < 0 || r >= m || c >= n || b[r][c] != 'O') return;
        b[r][c] = '#';
        dfs(b, r + 1, c);
        dfs(b, r - 1, c);
        dfs(b, r, c + 1);
        dfs(b, r, c - 1);
    }
};

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or c < 0 or r >= m or c >= n or 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 i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

var solve = function(board) {
  const m = board.length;
  if (m === 0) return;
  const n = board[0].length;

  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= m || c >= n || 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 (let i = 0; i < m; i++) {
    dfs(i, 0);
    dfs(i, n - 1);
  }
  for (let j = 0; j < n; j++) {
    dfs(0, j);
    dfs(m - 1, j);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      else if (board[i][j] === '#') board[i][j] = 'O';
    }
  }
};

中文

题目概述

给定一个只包含 'X' 和 'O' 的矩阵，把所有被 'X' 完全包围的区域改成 'X'。

核心思路

关键不是直接找“被包围”的 'O'，而是先找“不能被包围”的 'O'：凡是与边界 'O' 连通的格子都必须保留。

最优算法步骤

1）扫描四条边，遇到 'O' 就做 DFS/BFS，把整块连通区域标记为临时字符 '#'。
2）全图扫描：剩余 'O' 一定是被包围的，改成 'X'。
3）把 '#' 还原成 'O'。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)（递归栈/队列最坏情况）。

常见陷阱

- 在标记阶段直接翻转为 'X'，会破坏连通性判断。
- 漏扫某一条边。
- 忘记把临时标记还原。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] b, int r, int c) {
        int m = b.length, n = b[0].length;
        if (r < 0 || c < 0 || r >= m || c >= n || b[r][c] != 'O') return;
        b[r][c] = '#';
        dfs(b, r + 1, c);
        dfs(b, r - 1, c);
        dfs(b, r, c + 1);
        dfs(b, r, c - 1);
    }
}

func solve(board [][]byte) {
    m := len(board)
    if m == 0 {
        return
    }
    n := len(board[0])

    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || c < 0 || r >= m || c >= n || 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 i := 0; i < m; i++ {
        dfs(i, 0)
        dfs(i, n-1)
    }
    for j := 0; j < n; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();

        for (int i = 0; i < m; ++i) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>>& b, int r, int c) {
        int m = b.size(), n = b[0].size();
        if (r < 0 || c < 0 || r >= m || c >= n || b[r][c] != 'O') return;
        b[r][c] = '#';
        dfs(b, r + 1, c);
        dfs(b, r - 1, c);
        dfs(b, r, c + 1);
        dfs(b, r, c - 1);
    }
};

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if r < 0 or c < 0 or r >= m or c >= n or 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 i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

var solve = function(board) {
  const m = board.length;
  if (m === 0) return;
  const n = board[0].length;

  const dfs = (r, c) => {
    if (r < 0 || c < 0 || r >= m || c >= n || 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 (let i = 0; i < m; i++) {
    dfs(i, 0);
    dfs(i, n - 1);
  }
  for (let j = 0; j < n; j++) {
    dfs(0, j);
    dfs(m - 1, j);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      else if (board[i][j] === '#') board[i][j] = 'O';
    }
  }
};