A more concise solution with Union-Find Set


  • 0
    S
    class Solution {
    public:
        vector<int> pa;
        
        int find(int n) {
            return pa[n] == n ? n : pa[n] = find(pa[n]);
        }
        
        void unite(int n1, int n2) {
            int p1 = find(n1);
            int p2 = find(n2);
            if (p1 == pa.size()-1) {
                pa[p2] = p1;
            } else {
                pa[p1] = p2;
            }
        }
        
        void solve(vector<vector<char>>& board) {
            if (board.empty() || board[0].empty()) {
                return ;
            }
            pa.resize(board.size() * board[0].size()+1);
            for (int i = 0; i < pa.size(); ++i) {
                pa[i] = i;
            }
            for (int y = 0; y < board.size(); ++y) {
                for (int x = 0; x < board[y].size(); ++x) {
                    if (board[y][x] == 'X') {
                        continue;
                    }
                    if (x == 0 || y == 0 || y+1 == board.size() || x+1 == board[y].size()) {
                        unite(pa.size()-1, y*board[0].size()+x);
                    }
                    if (x > 0 && board[y][x-1] == 'O') {
                        unite(y*board[0].size()+x-1, y*board[0].size()+x);
                    }
                    if (y > 0 && board[y-1][x] == 'O') {
                        unite((y-1)*board[0].size()+x, y*board[0].size()+x);
                    }
                }
            }
            for (int y = 0; y < board.size(); ++y) {
                for (int x = 0; x < board[y].size(); ++x) {
                    if (board[y][x] == 'O' && find(y*board[0].size()+x) != pa.size()-1) {
                        board[y][x] = 'X';
                    }
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.