130. 被围绕的区域

题目描述

输入一个 m x n 的字符矩阵 board，每格是 "X" 或 "O"。

上下左右相邻的 "O" 连成一个区域。如果某个区域里没有任何一格位于矩阵最外一圈，这个区域就被 "X" 包围。

把所有被包围区域里的 "O" 改成 "X"；接触边界的区域保持不变。直接在 board 上修改，不需要返回值。

示例 1

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解释：中间三个 O 被包围，改成 X；最下面一行的 O 在边界上，保留。

示例 2

输入：board = [["X"]]
输出：[["X"]]

解释：没有 O，矩阵不变。

数据范围

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 是 "X" 或 "O"。

解题思路：边界出发 DFS

直接判断“被围住”很难，反过来找“没被围住”的：从边界上每个 "O" 出发 DFS，把能连到的 "O" 都临时改成 "#"。之后扫描全表：剩下的 "O" 一定被围住，改成 "X"；"#" 恢复成 "O"。

为什么正确

标记阶段结束时，"#" 恰好是与边界连通的所有 "O"，剩下的 "O" 都不与边界连通。

复杂度分析

时间 O(mn)，空间 O(mn)（递归栈最坏情况）。

易错点

不要在第一遍里边找边翻转：一个区域是否能碰到边界，要把整个区域走完才知道。先用 # 标记、最后统一翻转最稳妥。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 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 r in range(m):
            for c in range(n):
                if r in (0, m - 1) or c in (0, n - 1):
                    dfs(r, 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'

class Solution {
    int m, n;

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                    dfs(board, r, c);
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == '#') {
                    board[r][c] = 'O';
                }
            }
        }
    }

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

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        function<void(int, int)> dfs = [&](int r, int c) {
            if (r < 0 || r >= m || c < 0 || 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 (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                    dfs(r, c);
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == '#') {
                    board[r][c] = 'O';
                }
            }
        }
    }
};

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || r >= m || c < 0 || 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 r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if r == 0 || r == m-1 || c == 0 || c == n-1 {
				dfs(r, c)
			}
		}
	}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if board[r][c] == 'O' {
				board[r][c] = 'X'
			} else if board[r][c] == '#' {
				board[r][c] = 'O'
			}
		}
	}
}

var solve = function(board) {
    const m = board.length, n = board[0].length;
    const dfs = (r, c) => {
        if (r < 0 || r >= m || c < 0 || 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 r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (r === 0 || r === m - 1 || c === 0 || c === n - 1) {
                dfs(r, c);
            }
        }
    }
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (board[r][c] === 'O') {
                board[r][c] = 'X';
            } else if (board[r][c] === '#') {
                board[r][c] = 'O';
            }
        }
    }
};

function solve(board: string[][]): void {
    const m = board.length, n = board[0].length;
    const dfs = (r: number, c: number): void => {
        if (r < 0 || r >= m || c < 0 || 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 r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (r === 0 || r === m - 1 || c === 0 || c === n - 1) {
                dfs(r, c);
            }
        }
    }
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (board[r][c] === 'O') {
                board[r][c] = 'X';
            } else if (board[r][c] === '#') {
                board[r][c] = 'O';
            }
        }
    }
}

载入编辑器，自己跑一遍 →

其他解法

两种解法都从边界标记安全区域，复杂度相同；DFS 写法更短，BFS 不受递归深度限制。

解法 2：边界出发 BFS 时间 O(m·n)，空间 O(m·n)

把边界上所有 'O' 标成 '#' 并放入队列。从队列中取出格子，把四周相邻的 'O' 也标成 '#' 并入队。最后遍历棋盘，剩余的 'O' 改成 'X'，'#' 还原成 'O'。

没有递归，大片连通区域不会栈溢出。需要显式队列和方向数组，代码稍长。

from collections import deque
from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])
        q = deque()
        for r in range(m):
            for c in range(n):
                if (r in (0, m - 1) or c in (0, n - 1)) and board[r][c] == 'O':
                    board[r][c] = '#'
                    q.append((r, c))
        while q:
            r, c = q.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'O':
                    board[nr][nc] = '#'
                    q.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'

class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if ((r == 0 || r == m - 1 || c == 0 || c == n - 1) && board[r][c] == 'O') {
                    board[r][c] = '#';
                    q.offer(new int[]{r, c});
                }
            }
        }
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int nr = cur[0] + dr[k], nc = cur[1] + dc[k];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
                    board[nr][nc] = '#';
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                else if (board[r][c] == '#') board[r][c] = 'O';
            }
        }
    }
}

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        queue<pair<int, int>> q;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if ((r == 0 || r == m - 1 || c == 0 || c == n - 1) && board[r][c] == 'O') {
                    board[r][c] = '#';
                    q.push({r, c});
                }
            }
        }
        int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
                    board[nr][nc] = '#';
                    q.push({nr, nc});
                }
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                else if (board[r][c] == '#') board[r][c] = 'O';
            }
        }
    }
};

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	q := [][2]int{}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if (r == 0 || r == m-1 || c == 0 || c == n-1) && board[r][c] == 'O' {
				board[r][c] = '#'
				q = append(q, [2]int{r, c})
			}
		}
	}
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		for _, d := range dirs {
			nr, nc := cur[0]+d[0], cur[1]+d[1]
			if nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O' {
				board[nr][nc] = '#'
				q = append(q, [2]int{nr, nc})
			}
		}
	}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if board[r][c] == 'O' {
				board[r][c] = 'X'
			} else if board[r][c] == '#' {
				board[r][c] = 'O'
			}
		}
	}
}

var solve = function(board) {
    const m = board.length, n = board[0].length;
    const q = [];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if ((r === 0 || r === m - 1 || c === 0 || c === n - 1) && board[r][c] === 'O') {
                board[r][c] = '#';
                q.push([r, c]);
            }
        }
    }
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (let head = 0; head < q.length; head++) {
        const [r, c] = q[head];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] === 'O') {
                board[nr][nc] = '#';
                q.push([nr, nc]);
            }
        }
    }
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (board[r][c] === 'O') board[r][c] = 'X';
            else if (board[r][c] === '#') board[r][c] = 'O';
        }
    }
};

function solve(board: string[][]): void {
    const m = board.length, n = board[0].length;
    const q: [number, number][] = [];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if ((r === 0 || r === m - 1 || c === 0 || c === n - 1) && board[r][c] === 'O') {
                board[r][c] = '#';
                q.push([r, c]);
            }
        }
    }
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (let head = 0; head < q.length; head++) {
        const [r, c] = q[head];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] === 'O') {
                board[nr][nc] = '#';
                q.push([nr, nc]);
            }
        }
    }
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (board[r][c] === 'O') board[r][c] = 'X';
            else if (board[r][c] === '#') board[r][c] = 'O';
        }
    }
}

图论专题的其他题目

查看图论全部题目 →