数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在 Python 中查找二维矩阵中不同岛屿的数量
假设我们有一个二进制矩阵。我们必须计算其中的岛屿数量。岛屿是指被水包围且通过水平或垂直连接相邻陆地形成的地方。我们可以假设网格的所有四个边缘都被水包围。
假设网格如下：
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
共有三个岛屿。
为了解决这个问题，我们将遵循以下步骤：
将有两种方法，一种用于计算岛屿数量，称为 numIslands() 和 makeWater()。makeWater() 将如下所示：
如果网格的行数为 0，则返回 0
n = 行数，m = 列数，ans = 0
对于 i 从 0 到 n – 1
对于 j 从 0 到 m
如果 grid[i, j] = 1，则 ans = ans + 1
makeWater(i, j, n, m, grid)
makeWater() 将接收索引 i、j、行数和列数 n 和 m 以及网格
如果 i < 0 或 j < 0 或 i >= n 或 j >= m，则从此方法返回
如果 grid[i, j] = 0，则返回；否则，将 grid[i, j] 设置为 0
调用 makeWater(i + 1, j, n, m, grid)
调用 makeWater(i, j + 1, n, m, grid)
示例
让我们看看下面的实现以更好地理解：
class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ if len(grid) == 0: return 0 n= len(grid) m = len(grid[0]) ans = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": ans+=1 self.make_water(i,j,n,m,grid) return ans def make_water(self,i,j,n,m,grid): if i<0 or j<0 or i>=n or j>=m: return if grid[i][j] == "0": return else: grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water(i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,grid)
输入
[["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]
输出
3
更新于：2020年8月27日
455 次查看
广告