Leetcode 【200、695】

问题描述：【DFS】200. Number of Islands

解题思路：

求二维矩阵中由 '1' 连通的岛屿个数（上下左右有 '1' 视为连通）。很明显用回溯法（DFS）求解。
（1）在递归回溯的函数外部，遍历二维矩阵，如果某个位置为 '1'，则将岛屿个数加 1，并调用回溯函数。
（2）在递归回溯的函数内部，将 '1' 的位置修改为 '0'（防止重复搜索），对上、下、左、右、四个方向进行搜索（注意边界情况），如果某个位置为 '1'，则继续回溯；否则结束。

Python3 实现：

class Solution:
    def __init__(self):
        self.pos = [[-1,0],[1,0],[0,-1],[0,1]]  # 上、下、左、右四个方向的相对位置
    
    def numIslands(self, grid: List[List[str]]) -> int:
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    ans += 1  # 有'1'，则岛屿数加1
                    self.search(grid, i, j)
        return ans
                    
    def search(self, grid, i, j):
        grid[i][j] = '0'  # 将'1'变成'0'，防止重复搜索
        for p in self.pos:
            if i+p[0] >= 0 and i+p[0] < len(grid) and j+p[1] >= 0 and j+p[1] < len(grid[0]) and grid[i+p[0]][j+p[1]] == '1':
                self.search(grid, i+p[0], j+p[1])

问题描述：【DFS】695. Max Area of Island

解题思路：

求二维矩阵中由 1 连通的岛屿最大面积（上下左右有 1 视为连通）。很明显用回溯法（DFS）求解。
（1）在递归回溯的函数外部，遍历二维矩阵，如果某个位置为 '1'，则调用回溯函数，更新岛屿的最大面积。
（2）在递归回溯的函数内部，边界情况是如果 grid[i][j] = 0，则返回 0，表示上、下、左、右四个方向都没有 1 了，面积为 0；否则，将 grid[i][j] 由 1 改成 0（防止重复搜索），同时设当前岛屿面积 ans = 1；然后，对上、下、左、右、四个方向进行搜索（注意边界情况），并递归调用该函数累加当前岛屿面积 ans；最后，返回 ans，就是当前连通岛屿的最大面积。

Python3 实现：

class Solution:
    def __init__(self):
        self.pos = [[-1,0], [1,0], [0,-1], [0,1]]  # 上、下、左、右四个方向的相对位置
        
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_area = max(max_area, self.search(grid, i, j))
        return max_area
    
    def search(self, grid, i, j):
        if grid[i][j] == 0:  # 上、下、左、右四个方向都没有 1 了，面积为 0
            return 0
        ans = 1  # 面积置为 1，因为已经youl
        grid[i][j] = 0  # 将'1'变成'0'，防止重复搜索
        for p in self.pos:
            if 0 <= i+p[0] < len(grid) and 0 <= j+p[1] < len(grid[0]):
                ans += self.search(grid, i+p[0], j+p[1])  # 累加面积
        return ans  # 当前岛屿的最大面积