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.

Have you met this question in a real interview?

Yes

Example

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

After capture all regions surrounded by'X', the board should be:

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

column size

check each line right away after writing down

class Solution {

public:

/\*\*

 \* @param board a 2D board containing 'X' and 'O'

 \* @return void

 \*/

void surroundedRegions\(vector<vector<char>>& board\) {

    // Write your code here

    if \(board.empty\(\) \|\| board\[0\].empty\(\)\) {

        return;

    }

    int n = board.size\(\);

    int m = board\[0\].size\(\);

    //cout << n << " " << m << endl; 

    parent.resize\(n\*m+1\);

    std::iota\(parent.begin\(\), parent.end\(\), 0\);

    int dummy = n\*m;

    vector<vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};

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

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

            if \(board\[i\]\[j\] == 'O'\) {

                if \(isOnBorder\(i, j, n, m\)\) {

                    Union\(convertToId\(i, j, m\), dummy\);    

                } else {

                    for \(auto dir : dirs\) {

                        int ni = i + dir\[0\];

                        int nj = j + dir\[1\];

                        if \(isInside\(ni, nj, n, m\) && board\[ni\]\[nj\] == 'O'\) {

                            Union\(convertToId\(i, j, m\), convertToId\(ni, nj, m\)\);

                        }

                    }

                }

            }

        }

    }

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

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

            if \(board\[i\]\[j\] == 'O' && cfind\(convertToId\(i, j, m\)\) != cfind\(dummy\)\) {

                board\[i\]\[j\] = 'X';

            }       

        }

    }

}

private:

bool isOnBorder\(int i, int j, int n, int m\) {

    return \(i == 0\) \|\| \(i == n-1\) \|\| \(j == 0\) \|\| \(j == m-1\);

}

bool isInside\(int i, int j, int n, int m\) {

    return \(i >= 0\) && \(i < n\) && \(j >= 0\) && \(j < m\);

}

int convertToId\(int i, int j, int m\) {

    return i\*m + j;

}

vector<int> parent;

int cfind\(int i\) {

    int fa = i;

    while \(parent\[fa\] != fa\) {

        fa = parent\[fa\];

    }

    while \(parent\[i\] != i\) {

        int temp = parent\[i\];

        parent\[i\] = fa;

        i = temp;

    }

    return fa;

}

int find\(int i\) {

    while \(parent\[i\] != i\) {

        i = parent\[i\];

    }

    return i;

}

void Union\(int a, int b\) {

    int pa = cfind\(a\);

    int pb = cfind\(b\);

    if \(pa != pb\) {

        parent\[pa\] = pb;

    }

}

};

results matching ""

    No results matching ""