Leetcode|DFS|130. 被围绕的区域

SL_World

发布于 2021-09-22 11:20:36

3750

文章被收录于专栏：XX

1 DFS

遍历棋盘边界，将边界对应的所有O进行dfs遍历成#
遍历棋盘，将所有中间O遍历成X
遍历棋盘，将所有中间#恢复成O

class Solution {
public:
    int n, m;
    void dfs(vector<vector<char>>& board, int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m || board[x][y] != 'O') return;
        board[x][y] = '#';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }

    void solve(vector<vector<char>>& board) {
        n = board.size();
        m = board[0].size();
        // 第1行和最后1行中的O进行dfs变成其他图标
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][m - 1] == 'O')  dfs(board, i, m - 1);
        }
        // 第1列和最后1列中的O进行dfs变成其他图标
        for (int i = 0; i < m; i++) {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[n - 1][i] == 'O')  dfs(board, n - 1, i);
        }
        // 将所有O变成X（可优化i从1开始遍历）
        for (int i = 1; i < n - 1; i++)
            for (int j = 1; j < m - 1; j++) 
                if (board[i][j] == 'O') board[i][j] = 'X';
        // 将所有#恢复成O
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) 
                if (board[i][j] == '#') board[i][j] = 'O'; 
    }
};