【leetcode】200. 岛屿数量

题目

200. 岛屿数量

题解

1. 深度优先搜索

1. 定义边界
2. 判断是否为岛屿
3. 上下左右进行搜索

class Solution(object):def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""def dfs(grid, i, j):if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':returngrid[i][j] = '0'dfs(grid, i + 1, j)dfs(grid, i - 1, j)dfs(grid, i, j - 1)dfs(grid, i, j + 1)count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':dfs(grid, i, j)count += 1return count

2. 广度优先搜索

1. 定义边界
2. 定义队列，加入该点的上下左右
3. 进行搜索

class Solution(object):def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""def bfs(grid, i, j):queue = [[i, j]]while queue:i, j = queue.pop(0)if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':grid[i][j] = '0'queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '0': continuebfs(grid, i, j)count += 1return count