岛屿最大面积 one pass 解法求解

有一道岛屿题很高频，题目大概就是：让求最大的陆地面积，1表示陆地0表示水域。如果一圈陆地包围一片水域那么这块水域也算这个岛的面积。

这个题目第一反应是two passes。 第一次pass把四周的点遍历一下，然后遇到0，BFS或者DFS变成2。 第二次pass，碰到1就DFS，把相连的0和1都计算一下算面积求最大。
但是貌似有一种one pass的方法， 看了提示的解法大概是全盘遍历，以1开始dfs无论01向四面扩展计数找岛的面积，如果触及边界上的水域就返回-1表示无效，然后把四面valid的面积累加。我发现在DFS时候算面积的时候， 遇到0不太好处理。
这种情况比较好处理， DFS遇到0， 就只继续DFS 0。 然后判断0是否连接边界，下面这个情况可以算对。
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

但比如下面这种情况：
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

岛的面积应该是5，但是如果只能one pass，其余的1只跟中间的0相连， 我就写不出程序能算出5来。
不知道各位大佬有什么想法？？

多谢。

用union-find algorithm，记录每个union的sz和最大的sz，one pass。加上shortcut的trick之后，复杂度O(n*logn)

补充内容 (2021-04-12 05:52 +08:00):
岛中湖需要一点特殊处理。海水一般当作孤岛处理，如果四周都是陆地，则当作陆地一样，和周围陆地相连了，计入union的sz。

HughHe 发表于 2021-4-12 05:46
用union-find algorithm，记录每个union的sz和最大的sz，one pass。加上shortcut的trick之后，复杂度O(n*lo ...

恩，我觉得uf可行。

遍历整个数组， 边界的0和外围（比如id=-1）connect。 非边界1和up，left 1 connect。
不过遇到非边界的0，怎么处理，我还是不太清楚。。。

如果你方便提供一小段示范代码那是最好，哈哈

Onepass遇到0也dfs遇到1也dfs。遇到1正常dfs，遇到0在dfs的时候给他一次变成1的机会，且1不能变成0，一旦越出边界了就返回-1说明个0是连着边界的，只有当被1包着的时候才算数和max去比较。

大佬们都没有想法啊？？

不知道我的想法对不对，你在周围往里面DFS/BFS的时候，这其实就是DFS flood fill，这时你记录一共遍历了多少格子，然后剩下的格子数应该就是最大面积了，不然的话一定还可以继续往里走的

这道题我面试出过好几次 以我的经验看能写出2 pass的就已经算可以过了 1 pass我也没见过 当然了 这题现在已经不用了

Falldawn 发表于 2021-4-12 01:57
不知道我的想法对不对，你在周围往里面DFS/BFS的时候，这其实就是DFS flood fill，这时你记录一共遍历了多 ...

如果只有一个岛是可以的。但是题目里会有多个岛。

这题我也见过几次 一般能答出来two pass的解法就可以了 还没人问我one pass的解法..

其实第一反应里的解法虽然是two pass，但两次dfs访问的点集是互斥的，所以效率上和one pass（如果有的话）没什么差别吧

你把水的面积一遍BFS pass过了,减掉，剩下的就是陆地面积
算水的面积，用最外围一圈的水，BFS标记就行了

因为但凡你最外围的水BFS不到的地方，都是陆地或者内湖