这题咋看上去很难,但实际上用“时光倒流”的想法就很方便。
假想在所有的erasure完成之后,这些砖块有些与top相连(成为大陆)),有些则是孤立的岛屿。我们考察最后一次抽掉的砖块,如果“复原”它能使得一些孤立的岛屿与大陆相连的话,那么这些岛屿的面积S,其实就是最后一次erasure所造成砖块掉落的数量。OK,就算这次“复原”不能使得任何岛屿与大陆相连,但也有可能会使得一部分岛屿之间相连,这样下一次“复原”的时候就有可能使得这一块更大的岛屿与大陆相连。以此方法不停地往回追溯上去。
此题我觉得用DFS来做更直观一点。我的做法是:
1.将所有的要被erasure的砖块都抹去,也就是标记0(这里我标记为-1便于与原先真正的“海洋”区别)。
2.用DFS的方法确定所有与上顶端相连的“大陆”,标记为2.
3.“时光倒流”,处理最后一次erasure。如果这个砖块的周围有大陆(标记是2),那么它就可能将一部分岛屿(标记是1)与大陆相连。所以从该点出发进行DFS,找出所有标记是1的格子,就是答案(也就是因为这次erasure造成的砖块掉落的数量),记得将这些已经并入大陆的格子也都标记成2。如果这个砖块的周围没有大陆,那么就简单的将这个位置的的标记恢复为1就行(也就是岛屿)。
- 依次类推处理所有的erasure。