算法笔试-网格图

Updated Time	2024-11-30
Category	算法
Tags

关于语言：一刷用 Golang，二刷用 Rust

题单来源于：分享丨【题单】网格图（DFS/BFS/综合应用））

网格图

题单

网格图 DFS

适用于需要计算连通块个数、大小的题目。

题目	来源	难度	分数
200. 岛屿数量		中等
695. 岛屿的最大面积		中等
面试题 16.19. 水域大小		中等
463. 岛屿的周长		简单
2658. 网格图中鱼的最大数目	第 103 场双周赛 Q3	中等	1490

题解

200. 岛屿数量

var (
    dx = [4]int{0, -1, 0, 1}
    dy = [4]int{-1, 0, 1, 0}
)
func numIslands(grid [][]byte) (ans int) {
    n, m := len(grid), len(grid[0])
    var dfs func(i, j int)
    dfs = func(i, j int) {
        grid[i][j] = '0'
        for d := range dx {
            x, y := i + dx[d], j + dy[d]
            if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0' {
                continue
            }
            dfs(x, y)
        }
    }
    for i := range grid {
        for j, v := range grid[i] {
            if v == '1' {
                dfs(i, j)
                ans++
            }
        }
    } 
    return
}

695. 岛屿的最大面积

func maxAreaOfIsland(grid [][]int) (ans int) {
    dx := []int{0, -1, 0, 1}
    dy := []int{-1, 0, 1, 0}
    n, m := len(grid), len(grid[0])
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        grid[i][j] = 0
        cnt := 1
        for d := range dx {
            x, y := i + dx[d], j + dy[d]
            if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0 {
                continue
            }
            cnt += dfs(x, y)
        }
        return cnt
    }
    for i := range grid {
        for j, v := range grid[i] {
            if v == 1 {
                ans = max(ans, dfs(i, j))
            }
        }
    }
    return
}

面试题 16.19. 水域大小

func pondSizes(land [][]int) []int {
    dx := []int{-1, 0, 1, -1 , 0, 1, -1, 0, 1}
    dy := []int{-1, -1, -1, 0, 0, 0, 1, 1, 1}
    n, m := len(land), len(land[0])
    ans := make([]int, 0)
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        cnt := 1
        land[i][j] = 1
        for d := range dx {
            x, y := i + dx[d], j + dy[d]
            if x < 0 || x >= n || y < 0 || y >= m || land[x][y] != 0 {
                continue
            }
            cnt += dfs(x, y)
        }
        return cnt
    }
    for i := range land {
        for j, v := range land[i] {
            if v == 0 {
                ans = append(ans, dfs(i, j))
            }
        }
    }
    sort.Ints(ans)
    return ans
}

463. 岛屿的周长

func islandPerimeter(grid [][]int) int {
    var dx = []int{-1, 0, 1, 0}
    var dy = []int{0, -1, 0, 1}
    n, m := len(grid), len(grid[0])
    vis := make([][]bool, n)
    for i := range vis {
        vis[i] = make([]bool, m)
    }
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        vis[i][j] = true
        cnt := 4
        for d := range dx {
            x, y := i + dx[d], j + dy[d]
            if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0 {
                continue
            }
            if vis[x][y] {
                cnt--
            } else {
                cnt += dfs(x, y) - 1
            }
        }
        return cnt
    }
    for i := range grid {
        for j, v := range grid[i] {
            if v == 1 {
                return dfs(i, j)
            }
        }
    } 
    return 0
}

2658. 网格图中鱼的最大数目

func findMaxFish(grid [][]int) (ans int) {
    var dx = []int{-1, 0, 1, 0}
    var dy = []int{0, -1, 0, 1}
    n, m := len(grid), len(grid[0])
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        cnt := grid[i][j]
        grid[i][j] = 0
        for d := range dx {
            x, y := i + dx[d], j + dy[d]
            if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0 {
                continue
            }
            cnt += dfs(x, y)
        }
        return cnt
    } 

    for i := range grid {
        for j := range grid[i] {
            if grid[i][j] != 0 {
                ans = max(ans, dfs(i, j))
            }
        }
    }
    return
}

1. 网格图
1. 1.1. 题单
  1. 1.1.1. 网格图 DFS
2. 1.2. 题解