当前位置：首页 > article >正文

【LeetCode】803、打砖块

article 2025/1/6 20:36:59

【LeetCode】803、打砖块

文章目录

一、洪水填充DFS、时光倒流
- 1.1 洪水填充DFS、时光倒流
二、多语言解法

一、洪水填充DFS、时光倒流

1.1 洪水填充DFS、时光倒流

先让炮弹打到的位置值-1
天花板第一行, 把 “值1” 洪水填充为 “值2”
时光倒流: 逆时间顺序, 把炮弹打到的位置值+1, 若该格子的值为1则把"值1"洪水填充为"值2", 看能增加几个"值2", 就是该格子消除后能掉落几个砖块

第三步, 要排除自己的砖块

// go
func hitBricks(g [][]int, hits [][]int) []int {
    m, n := len(g), len(g[0])
    ans := make([]int, len(hits))
    if m == 1 {return ans}

    for _, h := range hits { // 炮弹位置值-1
        g[h[0]][h[1]]--
    }

    var dfs func(i,j int) int
    dfs = func(i,j int) int {
        if i < 0 || i == m || j < 0 || j == n || g[i][j] != 1 {return 0}
        g[i][j] = 2
        return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1)
    }
    for j := range n { // 天花板洪水填充
        if g[0][j] == 1 {
            dfs(0,j)
        }
    }

    worth := func(i,j int) bool { // 是否值得 时光倒流 时的洪水填充
        return g[i][j] == 1 && (i == 0 || (i > 0 && g[i-1][j] == 2) || (i < m-1 && g[i+1][j] == 2) || (j > 0 && g[i][j-1] == 2) || (j < n-1 && g[i][j+1] == 2))
    }
    for k := len(hits)-1; k >= 0; k-- { // 时光倒流 逆时间顺序 处理每个炮弹
        h := hits[k]
        i,j := h[0],h[1]
        g[i][j]++
        if worth(i,j) {
            ans[k] = dfs(i,j)-1
        }
    }
    return ans
}