Question

694. 不同岛屿的数量

English Version

题目描述

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

 

示例 1：

输入: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
输出：1

示例 2：

输入: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
输出: 3

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 仅包含 0 或 1

解法

方法一：哈希表 + DFS

我们遍历网格中的每个位置 $(i, j)$，如果该位置为 $1$，则以其为起始节点开始进行深度优先搜索，过程中将 $1$ 修改为 $0$，并且将搜索的方向记录下来，等搜索结束后将方向序列加入哈希表中，最后返回哈希表中不同方向序列的数量即可。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别为网格的行数和列数。

class Solution:
  def numDistinctIslands(self, grid: List[List[int]]) -> int:
    def dfs(i: int, j: int, k: int):
      grid[i][j] = 0
      path.append(str(k))
      dirs = (-1, 0, 1, 0, -1)
      for h in range(1, 5):
        x, y = i + dirs[h - 1], j + dirs[h]
        if 0 <= x < m and 0 <= y < n and grid[x][y]:
          dfs(x, y, h)
      path.append(str(-k))

    paths = set()
    path = []
    m, n = len(grid), len(grid[0])
    for i, row in enumerate(grid):
      for j, x in enumerate(row):
        if x:
          dfs(i, j, 0)
          paths.add("".join(path))
          path.clear()
    return len(paths)

class Solution {
  private int m;
  private int n;
  private int[][] grid;
  private StringBuilder path = new StringBuilder();

  public int numDistinctIslands(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    Set<String> paths = new HashSet<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          dfs(i, j, 0);
          paths.add(path.toString());
          path.setLength(0);
        }
      }
    }
    return paths.size();
  }

  private void dfs(int i, int j, int k) {
    grid[i][j] = 0;
    path.append(k);
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int h = 1; h < 5; ++h) {
      int x = i + dirs[h - 1];
      int y = j + dirs[h];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y, h);
      }
    }
    path.append(k);
  }
}

class Solution {
public:
  int numDistinctIslands(vector<vector<int>>& grid) {
    unordered_set<string> paths;
    string path;
    int m = grid.size(), n = grid[0].size();
    int dirs[5] = {-1, 0, 1, 0, -1};

    function<void(int, int, int)> dfs = [&](int i, int j, int k) {
      grid[i][j] = 0;
      path += to_string(k);
      for (int h = 1; h < 5; ++h) {
        int x = i + dirs[h - 1], y = j + dirs[h];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
          dfs(x, y, h);
        }
      }
      path += to_string(k);
    };

    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          dfs(i, j, 0);
          paths.insert(path);
          path.clear();
        }
      }
    }
    return paths.size();
  }
};

func numDistinctIslands(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  paths := map[string]bool{}
  path := []byte{}
  dirs := [5]int{-1, 0, 1, 0, -1}
  var dfs func(i, j, k int)
  dfs = func(i, j, k int) {
    grid[i][j] = 0
    path = append(path, byte(k))
    for h := 1; h < 5; h++ {
      x, y := i+dirs[h-1], j+dirs[h]
      if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
        dfs(x, y, h)
      }
    }
    path = append(path, byte(k))
  }
  for i, row := range grid {
    for j, x := range row {
      if x == 1 {
        dfs(i, j, 0)
        paths[string(path)] = true
        path = path[:0]
      }
    }
  }
  return len(paths)
}

function numDistinctIslands(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const paths: Set<string> = new Set();
  const path: number[] = [];
  const dirs: number[] = [-1, 0, 1, 0, -1];
  const dfs = (i: number, j: number, k: number) => {
    grid[i][j] = 0;
    path.push(k);
    for (let h = 1; h < 5; ++h) {
      const [x, y] = [i + dirs[h - 1], j + dirs[h]];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
        dfs(x, y, h);
      }
    }
    path.push(k);
  };
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j]) {
        dfs(i, j, 0);
        paths.add(path.join(','));
        path.length = 0;
      }
    }
  }
  return paths.size;
}