CF1829E The Lakes 题解

· · 题解

传送门
bfs 板子。
我们用普通的 bfs 求联通块板子就可以，但是需要记录每一个联通块的和。
这里讲讲如何用 bfs 求联通块。
我们设 vis_{i,j} 为是否访问过 a_{i,j}，访问过为 1，否则为 0。再设 sum 为本次答案，ans 为最终答案。
我们扫一遍 a，如果 a_{i,j}≠0 且 vis_{i,j}=0 我们就进行一轮 bfs 并记录下 sum。
记得每次开始 bfs 都要清空 sum，结束后要和 ans 取最大值。
CODE