Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 10

Description

Regions Cut By Slashes

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a '\' is represented as '\\'.

Example 1:

Input: grid = [" /","/ "]
Output: 2

Example 2:

Input: grid = [" /","  "]
Output: 1

Example 3:

Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 30
• grid[i][j] is either '/', '\', or ' '.

Solution

struct UnionSet {
  vector<int> parent;
public:
  int count;
  UnionSet(int size): parent(size), count(0) {
    iota(parent.begin(), parent.end(), 0);
  }

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

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) count += 1;
    parent[x] = y;
  }

  void resetCount() {
    count = 0;
  }
};
class Solution {
public:
  int regionsBySlashes(vector<string>& grid) {
    int n = grid.size();
    int dots = n + 1;
    UnionSet us(dots * dots);

    for(int i = 0; i < dots; ++i) {
      us.merge(0, i);
      us.merge(0, i * dots);
      us.merge(0, i * dots + dots - 1);
      us.merge(0, (dots * dots) - dots + i);
    }
    us.resetCount();

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        if(grid[i][j] == '\\') {
          us.merge(i * dots + j, (i + 1) * dots + j + 1);
        } else if (grid[i][j] == '/') {
          us.merge((i + 1) * dots + j, i * dots + j + 1);
        }
      }
    }
    return us.count + 1;
  }
};