链接：
https://leetcode-cn.com/problems/surrounded-regions/

题目

此题采用广度优先的思想：最外圈是‘O’的不能改变，与最外圈‘O’链接的‘O’不能改变。
整体上分3步：
1.把最外圈的‘O’找出来放到队列中，并把‘O’改成‘A’。
2.遍历整个队列，对于队列中的每个元素，如果它的上下左右是‘O’，那也把这个元素改成‘A’，并把这个元素放到队尾，同时把队首的元素弹出。
3.遍历整个数组，把所有的‘O’改成‘X’，把所有的‘A’改成‘O’。

class Solution {
public:
    void solve(vector<vector<char>>& board)
    {
        if (board.size() == 0 || board[0].size() == 0) {
            return;
        }
        top = 0;
        bottom = static_cast<int>(board.size()) - 1;
        left = 0;
        right = static_cast<int>(board[0].size()) - 1;
        while (!infectedPos.empty()) {
            infectedPos.pop();
        }

        PreProcess(board);
        DoProcess(board);
        PostProcess(board);
    }

private:
    // x为行数，y为列数
    struct Pos {
        int x;
        int y;
    };
    int top = -1;
    int bottom = -1;
    int left = -1;
    int right = -1;
    queue<Pos> infectedPos;

private:
    // 处理四周的节点，初始化队列
    void PreProcess(vector<vector<char>>& board)
    {
        for (int i = left; i <= right; i++) {
            if (board[top][i] == 'O') {
                board[top][i] = 'A';
                infectedPos.push({ top, i });
            }
            if (board[bottom][i] == 'O') {
                board[bottom][i] = 'A';
                infectedPos.push({ bottom, i });
            }
        }
        for (int i = top; i <= bottom; i++) {
            if (board[i][left] == 'O') {
                board[i][left] = 'A';
                infectedPos.push({ i, left });
            }
            if (board[i][right] == 'O') {
                board[i][right] = 'A';
                infectedPos.push({ i, right });
            }
        }
    }

    // 处理里边的点
    void DoProcess(vector<vector<char>>& board)
    {
        while (!infectedPos.empty()) {
            Pos& p = infectedPos.front();
            int x = p.x;
            int y = p.y;
            if (x > top) {
                if (board[x - 1][y] == 'O') {
                    board[x - 1][y] = 'A';
                    infectedPos.push({ x - 1, y });
                }
            }
            if (x < bottom) {
                if (board[x + 1][y] == 'O') {
                    board[x + 1][y] = 'A';
                    infectedPos.push({ x + 1, y });
                }
            }
            if (y > left) {
                if (board[x][y - 1] == 'O') {
                    board[x][y - 1] = 'A';
                    infectedPos.push({ x, y - 1 });
                }
            }
            if (y < right) {
                if (board[x][y + 1] == 'O') {
                    board[x][y + 1] = 'A';
                    infectedPos.push({ x, y + 1 });
                }
            }
            infectedPos.pop();
        }
    }

    // 算出最终结果
    void PostProcess(vector<vector<char>>& board)
    {
        for (int i = top; i <= bottom; i++) {
            for (int j = left; j <= right; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
};