讨论/技术交流/企鹅破冰-算法讨论/

工作上遇到一个算法题,想请教下大家有没有更好的思路。

题目如下:
市面上有一款企鹅破冰的游戏(penguins trap),它是由一些六边形的构成的平面。在这里我们先把问题简化成一个由m行和n列个正方形组成的一个矩形平面(1表示有砖块,0表是空),该矩形被固定的墙壁围起来。

我们假设砖块之间是有摩擦力,假设一个砖块对立的两条边都被挨着,那么它就不会掉落。

我们给定一个敲打前的矩阵,假设我们敲掉一个砖块,求剩下的砖块。

示例1:

敲打前

[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]
[1, 1, 1, 1, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]
我们敲打[2,2]坐标的砖块

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

示例2:

敲打前

[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]
[1, 1, 1, 1, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]
我们敲打[2,1]坐标的砖块

[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 1, 1, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0]

共 1 个回复

我目前的思路是:
每个砖块有4条边,我们需要对每个砖块的边进行标记,一旦存在对立的两条边都成功标记,则表示这个砖块是稳定的。一个稳定的砖块又可以继续以它为中心点继续标记它4个方向上的所有砖块。
遍历的方式我这边使用BFS,queue中的第一批元素正是包围着矩阵的墙壁。

时间复杂度O(mn(m+n)),不知道有没更好的算法