Regions Cut By Slashes Solutions in C++

/// Source : https://leetcode.com/problems/regions-cut-by-slashes/
/// Author : liuyubobobo
/// Time   : 2018-12-15

#include <iostream>
#include <vector>

using namespace std;


/// DFS
/// Time Complexity: O(4 * m * n)
/// Space Complexity: O(4 * m * n)
class Solution {

private:
    const int d[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int m, n;

public:
    int regionsBySlashes(vector<string>& grid) {

        m = grid.size(), n = grid[0].size();
        vector<vector<vector<bool>>> visited(m,
                vector<vector<bool>>(n, vector<bool>(4, false)));

        int res = 0;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                for(int k = 0; k < 4; k ++)
                    if(!visited[i][j][k])
                        res ++, dfs(grid, i, j, k, visited);
        return res;
    }

private:
    void dfs(const vector<string>& grid, int r, int c, int k,
             vector<vector<vector<bool>>>& visited){

        visited[r][c][k] = true;
        if(grid[r][c] == '/'){
            if(k < 2){
                if(!visited[r][c][1 - k]) dfs(grid, r, c, 1 - k, visited);
            }
            else{
                if(!visited[r][c][5 - k]) dfs(grid, r, c, 5 - k, visited);
            }
        }
        else if(grid[r][c] == '\\'){
            if(!visited[r][c][3 - k]) dfs(grid, r, c, 3 - k, visited);
        }
        else{
            for(int kk = 0; kk < 4; kk ++)
                if(!visited[r][c][kk])
                    dfs(grid, r, c, kk, visited);
        }

        int nextr = r + d[k][0], nextc = c + d[k][1];
        if(in_area(nextr, nextc)){
            if(k % 2){
                if(!visited[nextr][nextc][4 - k]) dfs(grid, nextr, nextc, 4 - k, visited);
            }
            else{
                if(!visited[nextr][nextc][2 - k]) dfs(grid, nextr, nextc, 2 - k, visited);
            }
        }
    }

    bool in_area(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/regions-cut-by-slashes/
/// Author : liuyubobobo
/// Time   : 2018-12-16

#include <iostream>
#include <vector>

using namespace std;


/// Union-Find
/// Time Complexity: O(4 * m * n)
/// Space Complexity: O(4 * m * n)
class UF{

private:
    vector<int> parent;
    int sz;

public:
    UF(int n){
        for(int i = 0 ; i < n ; i ++)
            parent.push_back(i);
        sz = n;
    }

    int find(int p){
        if( p != parent[p] )
            parent[p] = find( parent[p] );
        return parent[p];
    }

    bool isConnected(int p , int q){
        return find(p) == find(q);
    }

    void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
        sz --;
    }

    int size(){
        return sz;
    }
};

class Solution {

private:
    const int d[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int m, n;

public:
    int regionsBySlashes(vector<string>& grid) {

        m = grid.size(), n = grid[0].size();

        UF uf(m * n * 4);
        for(int r = 0; r < m; r ++)
            for(int c = 0; c < n; c ++)
                for(int k = 0; k < 4; k ++){
                    if(grid[r][c] == '/')
                        uf.unionElements(id(r, c, k), id(r, c, k < 2 ? 1 - k : 5 - k));
                    else if(grid[r][c] == '\\')
                        uf.unionElements(id(r, c, k), id(r, c, 3 - k));
                    else
                        for(int kk = 0; kk < 4; kk ++)
                            uf.unionElements(id(r, c, k), id(r, c, kk));

                    int nextr = r + d[k][0], nextc = c + d[k][1];
                    if(in_area(nextr, nextc))
                        uf.unionElements(id(r, c, k), id(nextr, nextc, k % 2 ? 4 - k : 2 - k));
                }
        return uf.size();
    }

private:
    int id(int r, int c, int k){
        return r * n * 4 + c * 4 + k;
    }

    bool in_area(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
};


int main() {

    return 0;
}