• 注册
  • 刷题上岸 刷题上岸 关注:2 内容:62

    200. Number of Islands

  • 查看作者
  • 打赏作者
    • 刷题上岸
    • Lv. 44
      VIP
      小可爱

      Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

      Example 1:

      Input:11110
      11010
      11000
      00000Output: 1

      Example 2:

      Input:11000
      11000
      00100
      00011Output: 3
      class Solution:
          def numIslands(self, grid: List[List[str]]) -> int:
              
              if not grid:
                  return 0
              
              nr, nc = len(grid), len(grid[0])
              ones = set()
              for i in range(nr):
                  for j in range(nc):
                      if grid[i][j] == '1':
                          ones.add((i,j))
              
              moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
              seen = set()
              n_island = 0
              for node in ones:
                  if node not in seen: # new network
                      seen.add(node)
                      queue = [node]
                      for ele in queue:
                          r, c = ele
                          for dr, dc in moves:
                              row, col = r + dr, c + dc
                              if (row, col) in ones and (row, col) not in seen:
                                  queue.append((row, col))
                                  seen.add((row, col))
                      n_island += 1
                      
              return n_island

      请登录之后再进行评论

      登录

      WordPress后台-外观-小工具 进行配置小工具

    • 做任务