数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：从给定矩阵中查找不同岛屿形状的数量
假设我们有一个二维二进制矩阵，我们需要找到给定矩阵中不同岛屿的数量。这里1代表陆地，0代表水，因此岛屿是一组相邻的1，其周边被水包围。如果两个岛屿的形状不同，则它们是唯一的。
因此，如果输入如下所示：
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
则输出将为4（不同岛屿以不同的颜色显示）。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数dfs()。这将接收i, j, k, l
mat[i, j] := 0
将(i − k, j − l)对插入到shape的末尾
如果 i + 1 < mat的行数 且 mat[i + 1, j] 为1，则
dfs(i + 1, j, k, l)
如果 j + 1 < mat的列数 且 mat[i, j + 1] 为1，则
dfs(i, j + 1, k, l)
如果 i − 1 >= 0 且 mat[i − 1, j] 为1，则
dfs(i − 1, j, k, l)
如果 j − 1 >= 0 且 mat[i, j − 1] 为1，则
dfs(i, j − 1, k, l)
在主方法中执行以下操作：
cnt := 0
shapes := 一个新的集合
对于 i 的范围从 0 到 mat 的行数，执行
对于 j 的范围从 0 到 mat 的列数，执行
如果 mat[i, j] 为 1，则
shape := 一个新的列表
dfs(i, j, i, j)
如果 shape 不在 shapes 中，则
cnt := cnt + 1
将 shape 插入到 shapes 中
返回 cnt
让我们看下面的实现来更好地理解：
示例
class Solution: def solve(self, mat): def dfs(i, j, k, l): mat[i][j] = 0 shape.append((i − k, j − l)) if i + 1 < len(mat) and mat[i + 1][j]: dfs(i + 1, j, k, l) if j + 1 < len(mat[0]) and mat[i][j + 1]: dfs(i, j + 1, k, l) if i − 1 >= 0 and mat[i − 1][j]: dfs(i − 1, j, k, l) if j − 1 >= 0 and mat[i][j − 1]: dfs(i, j − 1, k, l) cnt = 0 shapes = set() for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j]: shape = [] dfs(i, j, i, j) shape = tuple(shape) if shape not in shapes: cnt += 1 shapes.add(shape) return cnt ob = Solution() matrix = [ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ] print(ob.solve(matrix))
输入
[ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ]
输出
4
更新于：2020-12-26
242 次浏览
广告