blog/source/_posts/2020-04-21-leetcode-number-of-islands.md

title	date	tags	categories
leetcode-number-of-islands	2020-04-21 12:55:17		leetcode

200. 岛屿数量

题目

这种矩阵题现在第一反应就是用广度优先搜索做，类似之前算和0之间的距离那题。遍历矩阵，遇到 1 就将 1 改成 0，然后广度优先搜索找出 1 相邻的所有 1，这就是一个岛屿，以此类推。

import collections
class Solution:
  def numIslands(self, grid) -> int:
    rows = len(grid)
    if not rows:
      return 0
    cols = len(grid[0])
    islands = 0
    for r in range(rows):
      for l in range(cols):
        if grid[r][l] == '1':
          islands += 1
          grid[r][l] = '0'
          neighbors = collections.deque([(r, l)])
          while neighbors:
            x, y = neighbors.popleft()
            for x_, y_ in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
              if 0<=x_<rows and 0<=y_<cols and grid[x_][y_] == '1':
                neighbors.append([x_, y_])
                grid[x_][y_] = '0'
    return islands