• En
  • Signup
  • 刷题上岸
  • Today 0
  • Post 12
  • Followed 1
  • 捐助

    请在小工具里添加二维码

    刷题上岸 刷题上岸 关注:1 内容:12

    200. Number of Islands

  • 查看作者
  • 打赏作者
  • 拉黑名单
    • 刷题上岸
    • 等级6
      土豪

      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

      请登录之后再进行评论

      登录
    • Tasks
    • Current Activities
    • Back to Top