130. Surrounded Regions

• dfs
• bfs
• union-find

A 'O' will not be surrounded by all sides only if it is linked (directly or through another 'O') to a 'O' that is on the boundary row or column. This means that if all 4 boundaries have only 'X' then all the characters can be switched to 'X'

For example if your region is defined like this

XXXX
XOOX
XOOX
XXXX

then we can convert all the 'O' to'X's.

Solution: Run through the boundaries and perform dfs when you come across a 'O' . Switch all adjoining 'O' to another character. (I have chosen to switch them to 'Y'). This way all th e'O's that are not surrounded completely by 'X' are switched to 'Y's .

After simply run through the matrix again and switch all 'Y' to 'O' and all 'O' to 'X'.

Time Complexity: O(NM)

dfs

class Solution {
    void dfs(vector<vector<char>>& board, int x, int y) {
        if (board[x][y] != 'O') return;
        board[x][y] = 'Y';
        if (x > 1) dfs(board, x-1, y);
        if (x+2 < board.size()) dfs(board, x+1, y);
        if (y > 1) dfs(board, x, y-1);
        if (y+2 < board[0].size()) dfs(board, x, y+1);
    }
public:
    void solve(vector<vector<char>>& board) {
        // if board size is smaller than 2x2, no change
        int n = board.size(); 
        if (n <= 2) return;
        int m = board[0].size();
        if (m <= 2) return;

        // right border && left border
        for (int i = 0; i < n; ++i) {
            dfs(board, i, 0);
            dfs(board, i, m-1);
        }

        // up border && down border
        for (int j = 0; j < m; ++j) {
            dfs(board, 0, j);
            dfs(board, n-1, j);
        }

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

bfs

class Solution {
    void bfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = 'Y';
        queue<pair<int, int> > q;
        q.push({x,y});
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();


            if (x > 1 && board[x-1][y] == 'O') {
                q.push({x-1, y});
                board[x-1][y] = 'Y';
            }
            if (x+2 < board.size() && board[x+1][y] == 'O') {
                q.push({x+1, y});
                board[x+1][y] = 'Y';
            }
            if (y > 1 && board[x][y-1] == 'O') {
                q.push({x, y-1});
                board[x][y-1] = 'Y';
            }
            if (y+2 < board[0].size() && board[x][y+1] == 'O') {
                q.push({x, y+1});
                board[x][y+1] = 'Y';
            }
        }
    }

public:
    void solve(vector<vector<char>>& board) {
        // if board size is smaller than 2x2, no change
        int n = board.size(); 
        if (n <= 2) return;
        int m = board[0].size();
        if (m <= 2) return;

        // right border && left border
        for (int i = 0; i < n; ++i) {
            if (board[i][0] == 'O')
                bfs(board, i, 0);
            if (board[i][m-1] == 'O')
                bfs(board, i, m-1);
        }

        // up border && down border
        for (int j = 0; j < m; ++j) {
            if (board[0][j] == 'O')
                bfs(board, 0, j);
            if (board[n-1][j] == 'O')
                bfs(board, n-1, j);
        }

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

union-find

class Solution {
private:
    int* id, *sz;
    int root(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]]; // set id[i] to its grandparent
            i = id[i];
        }
        return i;
    }

    void unionT(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) return;
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }
    bool connected(int p, int q) {
        return root(p) == root(q);
    }
public:
    void solve(vector<vector<char>>& board) {
        int n = board.size();
        if (n <= 2) return;
        int m = board[0].size();
        if (m <= 2) return;

        int root = n*m;
        id = new int[root+1]; 
        sz = new int[root+1];
        for (int i = 0; i < root+1; ++i) {
            id[i] = i;
            sz[i] = 1;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {

                if (board[i][j] == 'O') {
                    //connected the root node to the edge 'O' nodes;
                    if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                        unionT(i*m+j, root);
                    } 
                    //connect the 'O' node to the right 'O' node and down 'O' node 
                    if (i < n - 1 && board[i + 1][j] == 'O') {
                        unionT(i*m+j, (i+1)*m+j);
                    }
                    if (j < m - 1 && board[i][j + 1] == 'O') {
                        unionT(i*m+j, i*m+j+1);
                    }
                }
            }
        }
         //check if 'O' connected to the root, if not change it to 'X'
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {
                   if (!connected(i*m+j, root)) {
                       board[i][j] = 'X';
                   }
                }
            }
        }
        delete[] id;
        delete[] sz;

    }
};