0803. Bricks Falling When Hit

题目信息

题号:

0803

难度:

Hard

主题:

网格、连通性、逐次移除

原题:

LeetCode 0803

重点:

砖块只有连接顶边或连接到稳定砖块时才稳定;每次敲击后统计因此掉落的砖块,不包含被直接敲掉的砖块

题目重述

给定一个由 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]
解释:目标格原本为空,网格结构没有变化,因此没有砖块掉落。