Question

959. Regions Cut By Slashes

中文文档

Description

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 ' '.

Solutions

Solution 1

class Solution:
  def regionsBySlashes(self, grid: List[str]) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    def union(a, b):
      pa, pb = find(a), find(b)
      if pa != pb:
        p[pa] = pb
        nonlocal size
        size -= 1

    n = len(grid)
    size = n * n * 4
    p = list(range(size))
    for i, row in enumerate(grid):
      for j, v in enumerate(row):
        k = i * n + j
        if i < n - 1:
          union(4 * k + 2, (k + n) * 4)
        if j < n - 1:
          union(4 * k + 1, (k + 1) * 4 + 3)
        if v == '/':
          union(4 * k, 4 * k + 3)
          union(4 * k + 1, 4 * k + 2)
        elif v == '\\':
          union(4 * k, 4 * k + 1)
          union(4 * k + 2, 4 * k + 3)
        else:
          union(4 * k, 4 * k + 1)
          union(4 * k + 1, 4 * k + 2)
          union(4 * k + 2, 4 * k + 3)
    return size

class Solution {
  private int[] p;
  private int size;

  public int regionsBySlashes(String[] grid) {
    int n = grid.length;
    size = n * n * 4;
    p = new int[size];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        int k = i * n + j;
        if (i < n - 1) {
          union(4 * k + 2, (k + n) * 4);
        }
        if (j < n - 1) {
          union(4 * k + 1, (k + 1) * 4 + 3);
        }
        char v = grid[i].charAt(j);
        if (v == '/') {
          union(4 * k, 4 * k + 3);
          union(4 * k + 1, 4 * k + 2);
        } else if (v == '\\') {
          union(4 * k, 4 * k + 1);
          union(4 * k + 2, 4 * k + 3);
        } else {
          union(4 * k, 4 * k + 1);
          union(4 * k + 1, 4 * k + 2);
          union(4 * k + 2, 4 * k + 3);
        }
      }
    }
    return size;
  }

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

  private void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) {
      return;
    }
    p[pa] = pb;
    --size;
  }
}

class Solution {
public:
  vector<int> p;
  int size;

  int regionsBySlashes(vector<string>& grid) {
    int n = grid.size();
    size = n * n * 4;
    p.resize(size);
    for (int i = 0; i < size; ++i) p[i] = i;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        int k = i * n + j;
        if (i < n - 1) merge(4 * k + 2, (k + n) * 4);
        if (j < n - 1) merge(4 * k + 1, (k + 1) * 4 + 3);
        char v = grid[i][j];
        if (v == '/') {
          merge(4 * k, 4 * k + 3);
          merge(4 * k + 1, 4 * k + 2);
        } else if (v == '\\') {
          merge(4 * k, 4 * k + 1);
          merge(4 * k + 2, 4 * k + 3);
        } else {
          merge(4 * k, 4 * k + 1);
          merge(4 * k + 1, 4 * k + 2);
          merge(4 * k + 2, 4 * k + 3);
        }
      }
    }
    return size;
  }

  void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) return;
    p[pa] = pb;
    --size;
  }

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

func regionsBySlashes(grid []string) int {
  n := len(grid)
  size := n * n * 4
  p := make([]int, size)
  for i := range p {
    p[i] = i
  }
  var find func(x int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  union := func(a, b int) {
    pa, pb := find(a), find(b)
    if pa == pb {
      return
    }
    p[pa] = pb
    size--
  }
  for i, row := range grid {
    for j, v := range row {
      k := i*n + j
      if i < n-1 {
        union(4*k+2, (k+n)*4)
      }
      if j < n-1 {
        union(4*k+1, (k+1)*4+3)
      }
      if v == '/' {
        union(4*k, 4*k+3)
        union(4*k+1, 4*k+2)
      } else if v == '\\' {
        union(4*k, 4*k+1)
        union(4*k+2, 4*k+3)
      } else {
        union(4*k, 4*k+1)
        union(4*k+1, 4*k+2)
        union(4*k+2, 4*k+3)
      }
    }
  }
  return size
}