封闭空间

大佬30行写出来的东西，硬是给我写了100行，欲哭无泪🥱

大佬写法

这里有一个很奇怪的问题，如果把row和col设置为私有变量，牛客会提示堆栈溢出，但是本地编译器没啥问题。本人才疏学浅，百思不得其姐，求大佬解答

class Solution {
public:
    void solve(vector> &board) {
        int row = board.size(), col = board[0].size();
        if (row < 3 || col < 3) return;
        // 行
        for (int i = 0; i < col; ++i) {
            dfs(board, 0, i);
            dfs(board, row - 1, i);
        }
        // 列
        for (int i = 1; i < row - 1; ++i) {
            dfs(board, i, 0);
            dfs(board, i, col - 1);
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                // 顺序不能反了
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '*') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector> &board, int i, int j) {
        if (i  board.size() - 1 || j  board[0].size() - 1) return;
        if (board[i][j] == 'O') {
            board[i][j] = '*';
            // 上下左右
            dfs(board, i - 1, j);
            dfs(board, i + 1, j);
            dfs(board, i, j - 1);
            dfs(board, i, j + 1);
        }
    }
};

渣渣写法

class Solution {
public:
    void solve(vector> &board) {
        // 思路：找出所有开放的点，将剩下的都设为'X'
        int row = board.size(), col = board[0].size();
        if (row <= 2 || col <= 2) return;
        // 第一行
        for (int i = 0; i < col; ++i) {
            pair loc(0, i);
            if (board[0][i] == 'O' && !isOpen(loc)) {
                findO(board, loc);
            }
        }
        // 最后一行
        for (int i = 0; i < col; ++i) {
            pair loc(row - 1, i);
            if (board[row - 1][i] == 'O' && !isOpen(loc)) {
                findO(board, loc);
            }
        }
        // 第一列
        for (int j = 1; j < row - 1; ++j) {
            pair loc(j, 0);
            if (board[j][0] == 'O' && !isOpen(loc)) {
                findO(board, loc);
            }
        }
        // 最后一列
        for (int j = 1; j < row - 1; ++j) {
            pair loc(j, col - 1);
            if (board[j][col - 1] == 'O' && !isOpen(loc)) {
                findO(board, loc);
            }
        }
        // 设置O
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                pair loc(i, j);
                if (board[i][j] == 'O' && !isOpen(loc)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
private:
    set> openLoc;
    void findO(vector> &board, pair &loc) {
        // 借助队列，广度优先遍历
        int row = board.size(), col = board[0].size();
        queue> record;
        record.push(loc);
        openLoc.insert(loc);
        while (!record.empty()) {
            pair current = record.front();
            record.pop();
            // 扫描上下左右，如有O，且没有记录在openLoc中，就推进去
            int x = current.first, y = current.second;
            int top = x - 1;
            int bottom = x + 1;
            int left = y - 1;
            int right = y + 1;
            loc.first = top;
            loc.second = y;
            if (top >= 0 && board[top][y] == 'O' && !isOpen(loc)) {
                record.push(loc);
                openLoc.insert(loc);
            }
            loc.first = bottom;
            loc.second = y;
            if (bottom < row && board[bottom][y] == 'O' && !isOpen(loc)) {
                record.push(loc);
                openLoc.insert(loc);
            }
            loc.first = x;
            loc.second = left;
            if (left >= 0 && board[x][left] == 'O' && !isOpen(loc)) {
                record.push(loc);
                openLoc.insert(loc);
            }
            loc.first = x;
            loc.second = right;
            if (right < col && board[x][right] == 'O' && !isOpen(loc)) {
                record.push(loc);
                openLoc.insert(loc);
            }
        }
    }
    bool isOpen(pair loc) {
        return !(openLoc.find(loc) == openLoc.end());
    }
};