原題
給一個(gè)01矩陣缺前，求不同的島嶼的個(gè)數(shù)。
0代表海悬襟，1代表島衅码，如果兩個(gè)1相鄰，那么這兩個(gè)1屬于同一個(gè)島脊岳。我們只考慮上下左右為相鄰逝段。
樣例
在矩陣：
[
[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 個(gè)島.
解題思路
- 本題就是無向圖中求連通塊的二維表示，所以同樣可以采用DFS解決割捅。使用Union Find大材小用了
- 設(shè)計(jì)一個(gè)removeIsland函數(shù)奶躯，每次遇到1就DFS進(jìn)行查找把上下左右相鄰的1都變成0
- 最后，兩層for循環(huán)遍歷二維數(shù)組亿驾，遇到1調(diào)用removeIsland函數(shù)
完整代碼
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
