【LeetCode 深度优先搜索专项】不同岛屿的数量（694）

文章目录

• 1. 题目
• • 1.1 示例
  • 1.2 说明
  • 1.3 提示
  • 1.4 进阶
• 2. 解法一（深度优先搜索）
• • 2.1 分析
  • 2.2 解答
  • 2.3 复杂度

1. 题目

给定一个 $m\times n$ 的二维矩阵 grid ，同时将由横向或纵向按边相接的 $1$ （代表陆地）所组成的集合视为岛屿，可以假定矩阵区域之外都为海水。

如果两个岛屿可以且仅可以通过平移的方式（不可进行旋转或镜像）覆盖相同的区域，就称这两个岛屿是相同的，要求返回 grid 中不同岛屿的数量。

1.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$

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/number-of-distinct-islands

1.3 提示

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 只会是 $0$ 或者 $1$

1.4 进阶

你可以使用多种方法解答这道题目么？（深度优先搜索、广度优先搜索）