原题
给一个01矩阵，求不同的岛屿的个数。
0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
样例
在矩阵：
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
中有 3 个岛.
解题思路
- 本题就是无向图中求连通块的二维表示，所以同样可以采用DFS解决。使用Union Find大材小用了
- 设计一个removeIsland函数，每次遇到1就DFS进行查找把上下左右相邻的1都变成0
- 最后，两层for循环遍历二维数组，遇到1调用removeIsland函数
完整代码
class Solution(object):
def __init__(self):
self.dx = [1, 0, 0, -1]
self.dy = [0, 1, -1, 0]
self.m = 0
self.n = 0
def removeIsland(self, grid, x, y):
grid[x][y] = '0';
for i in range(4):
nextX = x + self.dx[i]
nextY = y + self.dy[i]
if nextX >= 0 and nextX < self.n and nextY >= 0 and nextY < self.m:
if grid[nextX][nextY] == '1':
self.removeIsland(grid, nextX, nextY)
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
self.n = len(grid)
if self.n == 0:
return 0
self.m = len(grid[0])
if self.m == 0:
return 0
count = 0
for i in range(self.n):
for j in range(self.m):
if grid[i][j] == '1':
self.removeIsland(grid, i, j)
count += 1
return count
