hiho一下第245周《岛屿3》题目分析

1
3

《岛屿3》题目分析

本题是一道经典的并查集问题。

我们分析一下增加一块陆地之后,岛屿数量、面积和周长会如何变化。

如果新增的陆地上下左右都不与其他岛屿相连,那么这一块就是孤岛。显然岛屿数量+1、面积+1、周长+4。

否则,我们假设新增陆地上下左右总计与K个不同的岛屿相连。那么这K个不同岛屿会与新增陆地一起合并成一个岛屿。所以岛屿数量应当减去(K-1),面积+1。

至于周长,我们需要检查新增陆地块的4条边是不是连着海。如果总计K条连着海(也就是4-K条连着陆地),周长增加的长度应为:2K-4。

综上所述,我们需要随时知道某一个陆地块属于哪个岛屿,还需要合并岛屿;这些都能用并查集搞定。

1 answer(s)

0

数据有问题,有x, y = 1000的数据。。。

write answer 切换为英文 切换为中文


转发分享