在Python中编写程序以计算矩阵中被环绕岛屿的数量
假设我们有一个二进制矩阵。其中1表示陆地,0表示水。正如我们所知,一个岛屿是由聚在一起的1组成的,其周长被水包围。我们必须找到完全被包围的岛屿的数量。
因此,如果输入如下所示:
那么输出将为2,因为有三个岛屿,但其中两个被完全包围。
为了解决这个问题,我们将遵循以下步骤 −
- 定义一个函数dfs()。它将会带参数i,j
- 如果i和j不在矩阵的范围内,那么
- 返回False
- 如果矩阵[i,j]与0相同,那么
- 返回True
- 矩阵[i,j]:= 0
- a:= dfs(i + 1,j)
- b:= dfs(i – 1,j)
- c:= dfs(i,j + 1)
- d:= dfs(i,j – 1)
- 返回a和b和c和d
- 从主方法执行以下操作:
- R:=矩阵的行数,C:=矩阵的列数
- 答案:= 0
- 对于范围在0到R的i,做以下操作:
- 对于范围在0到C的j,做以下操作:
- 如果矩阵[i,j]与1相同,那么
- 如果dfs(i,j)为真,则
- 答案:=答案+1
- 对于范围在0到C的j,做以下操作:
- 返回答案
看下面的实现以更好地理解−
更多Python相关文章,请阅读:Python 教程
样例
class Solution:
def solve(self, matrix):
def dfs(i, j):
if i < 0 or j < 0 or i >= R or j >= C:
return False
if matrix[i][j] == 0:
return True
matrix[i][j] = 0
a = dfs(i + 1, j)
b = dfs(i - 1, j)
c = dfs(i, j + 1)
d = dfs(i, j - 1)
return a and b and c and d
R, C = len(matrix), len(matrix[0])
ans = 0
for i in range(R):
for j in range(C):
if matrix[i][j] == 1:
if dfs(i, j):
ans += 1
return ans
ob = Solution()
matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
print(ob.solve(matrix))
输入
matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0] ]
输出
2