[leetcode/lintcode 題解] 阿裡面試高頻題：島嶼的個數

描述

給一個 01 矩陣，求不同的島嶼的個數。

0 代表海，1 代表島，如果兩個 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           

樣例 2：
輸入：
[
  [1,1]
]
輸出：
1           

解題思路

用

九章算法班

中講到的 BFS 模闆。

源代碼

from collections import deque

DIRECTIONS = [(1, 0), (0, -1), (-1, 0), (0, 1)]

class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        if not grid or not grid[0]:
            return 0
            
        islands = 0
        visited = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and (i, j) not in visited:
                    self.bfs(grid, i, j, visited)
                    islands += 1
                    
        return islands                    
    
    def bfs(self, grid, x, y, visited):
        queue = deque([(x, y)])
        visited.add((x, y))
        while queue:
            x, y = queue.popleft()
            for delta_x, delta_y in DIRECTIONS:
                next_x = x + delta_x
                next_y = y + delta_y
                if not self.is_valid(grid, next_x, next_y, visited):
                    continue
                queue.append((next_x, next_y))
                visited.add((next_x, next_y))

    def is_valid(self, grid, x, y, visited):
        n, m = len(grid), len(grid[0])
        if not (0 <= x < n and 0 <= y < m):
            return False
        if (x, y) in visited:
            return False
        return grid[x][y]           

# LeetCode 的使用者請用下面的代碼，因為 LeetCode 上的輸入是 2D string array 而不是 boolean array
# from collections import deque

# class Solution:
#     """
#     @param grid: a boolean 2D matrix
#     @return: an integer
#     """
#     def numIslands(self, grid):
#         if not grid or not grid[0]:
#             return 0
        
#         islands = 0
#         for i in range(len(grid)):
#             for j in range(len(grid[0])):
#                 if grid[i][j] == '1':
#                     self.bfs(grid, i, j)
#                     islands += 1
                    
#         return islands                    
    
#     def bfs(self, grid, x, y):
#         queue = deque([(x, y)])
#         grid[x][y] = '0'
#         while queue:
#             x, y = queue.popleft()
#             for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
#                 next_x = x + delta_x
#                 next_y = y + delta_y
#                 if not self.is_valid(grid, next_x, next_y):
#                     continue
#                 queue.append((next_x, next_y))
#                 grid[next_x][next_y] = '0'
                
#     def is_valid(self, grid, x, y):
#         n, m = len(grid), len(grid[0])
#         return 0 <= x < n and 0 <= y < m and grid[x][y] == '1'           

更多題解參考：

九章官網solution