岛屿问题

【DFS】岛屿问题五连杀！ - 知乎

2024-04-29 momenta 面试考过的,竟然没有一点思路, 没想到这么简单的题竟然不会,难受了

leetcode 200 岛屿问题 -mid
没什么好注意的 (可能边界条件?)
想到 bfs 就能秒

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        def dfs(x, y):
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
                return
            if (grid[x][y]) == "0":
                return
            if (grid[x][y]) == "1":
                grid[x][y] = "0"
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
            return
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if (grid[i][j]) == "1":
                    dfs(i, j)
                    count += 1
        return count

leetcode 2054 闭合岛屿问题 -mid
这里注意选择 bfs 的对象由土地变成了水, 但水接触了边界后就返回错误.
也有另一种做法, 把所有接水的边上岛屿淹没, 感觉不如我这个想法

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
                return False
            if grid[i][j] == 1:
                return True
            if grid[i][j] == 0:
                grid[i][j] = 1
            left = dfs(i - 1, j)
            right = dfs(i + 1, j)
            up = dfs(i, j + 1)
            down = dfs(i, j - 1)
            sum = left and right and up and down
            return sum
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    solution = dfs(i, j)
                    if solution is True:
                        count += 1
        return count

leetcode 695 最大岛屿问题 -mid
没什么好注意的,非常简单

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_land = 0
        def dfs(i, j) -> int:
            curr_land = 0
            if i < 0 or j < 0 or len(grid) <= i or len(grid[0]) <= j:
                return 0
            if grid[i][j] == 0:
                return 0
            if grid[i][j] == 1:
                grid[i][j] = 0
                curr_land = 1
            left = dfs(i - 1, j)
            right = dfs(i + 1, j)
            up = dfs(i, j + 1)
            down = dfs(i, j - 1)
            sum = left + right + up + down + curr_land
            return sum
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_land = max(max_land, dfs(i, j))
        return max_land

leetcode 1905 子覆盖, 同一个思路

leetcode 463 岛屿周长:
算岛屿问题的一个另类, 但要注意这里面的思想, 并没有用到 dfs(虽然也可以用) 同时也要想办法尝试去解决这样的问题:
如: 最小岛屿周长
如: 最小闭合岛屿周长等, 要注意各种 combination

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        land = 0
        border = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    land += 1
                    if i + 1 < len(grid):
                        if (grid[i + 1][j]) == 1:
                            border += 1
                    if j + 1 < len(grid[0]):
                        if (grid[i][j + 1]) == 1:
                            border += 1
        return 4 * land - 2 * border

leetcode 1293-hard 打穿格子最短路径
想法是使用 DFS 做, 非常不幸, 失败了,于是决定用 BFS 做, 顺便开取了 BFS专题
还有注意形如
[[0]*10]*10 这样的二维数组生成方式是 python 陷阱, 正常应该用 [[0] * 40 for _ in range(40)]

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        max_int = 100
        visitid = [[0] * 40 for _ in range(40)]
        if k > len(grid) + len(grid[0]) - 2:
            return len(grid) + len(grid[0]) - 2
        def dfs(i, j, count, k):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
                return max_int
            if i == len(grid) - 1 and j == len(grid[0]) - 1:
                return count
            if visitid[i][j] == 1:
                return max_int
            if grid[i][j] == 1:
                if k > 0:
                    k -= 1
                else:
                    return max_int
            visitid[i][j] = 1
            count += 1
            left_min = dfs(i - 1, j, count, k)
            right_min = dfs(i + 1, j, count, k)
            up_min = dfs(i, j + 1, count, k)
            down_min = dfs(i, j - 1, count, k)
            visitid[i][j] = 0  # BACKTRACKING
            return min(left_min, right_min, up_min, down_min)
        answer = dfs(0, 0, 0, k)
        return -1 if answer == max_int else answer