130. Surrounded Regions

Difficulty: Medium

Frequency: N/A

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

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

For 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

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int width = board.size();
        if (!width) return;
        int length = board[0].size();
        if (!length) return;
        for (int i = 0; i < width; i++) {
            if (board[i][0] == 'O') flip(board, i, 0);
            if (board[i][length - 1] == 'O') flip(board, i, length - 1);
        }
        for (int j = 1; j < length - 1; j++) {
            if (board[0][j] == 'O') flip(board, 0, j);
            if (board[width - 1][j] == 'O') flip(board, width - 1, j);
        }
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i][j] == 'T') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
    void flip(vector<vector<char>>& board, int i, int j) {
        int width = board.size();
        int length = board[0].size();
        queue<pair<int, int>> myQ;
        myQ.push(make_pair(i, j));
        board[i][j] = 'T';
        while (!myQ.empty()) {
            pair<int, int> cur = myQ.front();
            myQ.pop();
            int p = cur.first, q = cur.second;
            if (p > 0 && board[p - 1][q] == 'O') {
                myQ.push(make_pair(p - 1, q));
                board[p - 1][q] = 'T';
            }
            if (p < width - 1 && board[p + 1][q] == 'O') {
                myQ.push(make_pair(p + 1, q));
                board[p + 1][q] = 'T';
            }
            if (q > 0 && board[p][q - 1] == 'O') {
                myQ.push(make_pair(p, q - 1));
                board[p][q - 1] = 'T';
            }
            if (q < length - 1 && board[p][q + 1] == 'O') {
                myQ.push(make_pair(p, q + 1));
                board[p][q + 1] = 'T';
            }
        }
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn: