0803. Bricks Falling When Hit¶
题目信息¶
- 题号:
0803
- 难度:
Hard
- 主题:
网格、连通性、逐次移除
- 原题:
- 重点:
砖块只有连接顶边或连接到稳定砖块时才稳定;每次敲击后统计因此掉落的砖块,不包含被直接敲掉的砖块
题目重述¶
给定一个由 0 和 1 组成的 m x n 网格 grid,其中 1 表示砖块。砖块只通过上、下、左、右相邻关系连接。位于第一行的砖块是稳定的;其他砖块只有能通过相邻砖块连接到第一行时才稳定。
按顺序执行数组 hits 中的敲击。每次敲击指定一个格子:若其中有砖块,就将该砖块移除;若原本为空,则网格不变。移除后,所有不再稳定的砖块会同时掉落并从网格中消失。请为每次敲击返回掉落砖块的数量,被直接敲掉的那一块不计入该数量。
1 <= m, n <= 200,1 <= hits.length <= 4 * 10^4;网格元素为 0 或 1,每个敲击坐标都在网格范围内,敲击位置互不重复。
自建示例¶
连续敲击分别切断两段支撑:
输入:grid = [[1,1,0],[0,1,1],[0,0,1]], hits = [[1,2],[0,1]]
输出:[1,1]
解释:第一次敲掉位置 (1,2) 后,位置 (2,2) 失去通往顶行的连接并掉落,所以计数为 1。此时位置 (1,1) 仍由顶行砖块 (0,1) 支撑;第二次直接敲掉 (0,1) 后,位置 (1,1) 随即掉落,因此第二项也是 1。两次被直接敲掉的砖都不计入答案。
敲击空格:
输入:grid = [[1,1],[0,1]], hits = [[1,0]]
输出:[0]
解释:目标格原本为空,网格结构没有变化,因此没有砖块掉落。