Could anyone help me correct my code?


  • 0

    I always get runtime error on OJ, although I can get correct result on my computer. I suspend it is because I use recursive Find(int x)??

    class UF{
    public:
        UF(int m, int n){
            count=0;
            id=vector<int> (m*n+1,-1);
        }
        int Find(int x){
            if(id[x]<0)
                return x;
            return id[x]=Find(id[x]);
        }
        void Union(int x,int y){
            int rootx=Find(x);
            int rooty=Find(y);
            if(rootx==rooty)
                return;
            if(id[rootx]>id[rooty]){
                id[rooty]+=id[rooty];
                id[rootx]=rooty;
            }
            else{
                id[rootx]+=id[rooty];
                id[rooty]=rootx;
            }
        }
        bool connected(int x,int y){
            return Find(x)==Find(y);
        }
    private:
        int count;
        vector<int> id;
    };
    
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if(board.empty())
                return;
            int m=board.size();
            int n=board[0].size();
            UF uf(m,n);
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(board[i][j]=='O'){
                        int p=i*n+j;
                        if(i==0||j==0||i==m-1||j==n-1){
                            uf.Union(p,m*n);
                        }
                        else{
                            if(board[i-1][j]=='O')
                                uf.Union(p,p-n);
                            if(board[i+1][j]=='O')
                                uf.Union(p,p+n);
                            if(board[i][j-1]=='O')
                                uf.Union(p,p-1);
                            if(board[i][j+1]=='O')
                                uf.Union(p,p+1);
                        }
                    }
                }
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(board[i][j]=='O'&&!uf.connected(i*n+j,m*n))
                        board[i][j]='X';
                }
            }
        }
    };
    

Log in to reply
 

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