130.md

被围绕的区域

题目: https://leetcode.cn/problems/surrounded-regions/

方法: 深度优先搜索, 需要从四周开始搜索.

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board[0].empty()) {
            return;
        }

        for (int row = 0; row < board.size(); row++) {
            dfs(board, row, 0);
            dfs(board, row, board[0].size() - 1);
        }
        for (int col = 0; col < board[0].size(); col++) {
            dfs(board, 0, col);
            dfs(board, board.size() - 1, col);
        }

        for (int row = 0; row < board.size(); row++) {
            for (int col = 0; col < board[0].size(); col++) {
                if (board[row][col] == 'O')  {
                    board[row][col] = 'X';
                }
                if (board[row][col] == NOT_SURROUNDED) {
                    board[row][col] = 'O';
                }
            }
        }
    }

private:
    const char NOT_SURROUNDED = '*';

    void dfs(vector<vector<char>> &board, int row, int col) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[row].size()) {
            return;
        }

        if (board[row][col] == 'O') {
            board[row][col] = NOT_SURROUNDED; // 标记.
            dfs(board, row + 1, col);
            dfs(board, row - 1, col);
            dfs(board, row, col + 1);
            dfs(board, row, col - 1);;
        }
    }
};