Question

959. 由斜杠划分区域

English Version

题目描述

在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。

给定网格 grid 表示为一个字符串数组，返回 _区域的数量_ 。

请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。

 

示例 1：

输入：grid = [" /","/ "]
输出：2

示例 2：

输入：grid = [" /","  "]
输出：1

示例 3：

输入：grid = ["/\\","\\/"]
输出：5
解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。

 

提示：

• n == grid.length == grid[i].length
• 1 <= n <= 30
• grid[i][j] 是 '/'、'\'、或 ' '

解法

方法一

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
}