题目
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.
解题思路
遍历这个矩阵，每次遇到1的时候意味着遇到了一个新的岛，结果加一，并从这个位置开始BSF/DFS把与他相邻的所有格子标成0，继续遍历
代码
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
grid[i][j] = '0'
q = [(i, j)]
while q:
x, y = q.pop()
if x > 0 and grid[x - 1][y] == '1':
grid[x - 1][y] = '0'
q.append((x - 1, y))
if y > 0 and grid[x][y - 1] == '1':
grid[x][y - 1] = '0'
q.append((x, y - 1))
if x < m - 1 and grid[x + 1][y] == '1':
grid[x + 1][y] = '0'
q.append((x + 1, y))
if y < n - 1 and grid[x][y + 1] == '1':
grid[x][y + 1] = '0'
q.append((x, y + 1))
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
res += 1
return res
