130.Surrounded Regions

Tags: Medium Depth-first Search Breadth-first Search Union Find

Links: https://leetcode.com/problems/surrounded-regions/

---

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

---

class Solution {
    int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    struct Node {
        int x, y;
        Node(int X, int Y) : x(X), y(Y) {}
    };
public:
    void solve(vector<vector<char>>& board) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = board.size(); if (!m) return;
        int n = board[0].size(); if (!n) return;

        queue<Node> q;
        for (int i = 0; i < n; ++i) {
            if (board[0][i] == 'O') q.push(Node(0, i)), board[0][i] = '#';
            if (m > 1 && board[m - 1][i] == 'O') q.push(Node(m - 1, i)), board[m - 1][i] = '#';
        }

        for (int i = 1; i < m - 1; ++i) {
            if (board[i][0] == 'O') q.push(Node(i, 0)), board[i][0] = '#';
            if (n > 1 && board[i][n - 1] == 'O') q.push(Node(i, n - 1)), board[i][n - 1] = '#';
        }

        while (!q.empty()) {
            Node tmp = q.front(); q.pop();

            for (int i = 0; i < 4; ++i) {
                int row = tmp.x + direction[i][0];
                int col = tmp.y + direction[i][1];
                if (0 <= row && row < m && 0 <= col && col < n && board[row][col] == 'O') {
                    board[row][col] = '#';
                    q.push(Node(row, col));
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

泛洪算法，规则就是如果在边界上的O，以及内部的O和边界上的O相连的不被填充，剩下的O都要被填充为X，所以需要正确区分O的不同类别，那么我们可以把不需要填充的O标记为#，然后遍历一遍矩阵，将余下的O填充为X，然后将#再转回O。

去不被填充的O的过程就是首先遍历四个边界，将边界上为O的点作为源点放入队列，然后就是很经典的传染病模型，用BFS去不断搜索需要入队的点。

时间复杂度$O(nm)$，空间复杂度可能存在矩阵所有的点都需要入队的情况，最坏为$O(nm)$