将原始网格中所有水田 'o' 按四方向(上、下、左、右)进行连通块划分,给每个水田格子分配一个组件编号,并记录每个组件的面积(格子数)。可用 BFS/DFS 完成,推荐 BFS 防止递归过深。
对于每一个格子:
'o',答案为 0(题意要求)。'x',把它视作改造成水田后,它会与其四邻中至多四个水田组件相连。取这些相邻组件编号的去重集合,把对应面积求和,再加上当前格子本身的 1,即为“将该位置改造成水田后,包含该位置的最大连通水田块大小”。这样即可一次预处理、一次扫描得到所有答案。
某地区有一片 n×m 的农田网格,每个格子要么是“旱田”(用 'x'表示,无法通水),要么是“水田”(用 'o'表示,可以通水)。水利部门计划对部分旱田进行改造,他们只能选择其中一块早田,将其改造成水田。
水利部门定义“连通水田块”指的是四连通区域(即区域内的任意两块水田可通过上下左右移动仅经过区域内的水田互相到达),“最大连通水田块”是指该区域在所有可能的连通水田块中面积最大(格子数量最多)。
水利部门希望先计算出不同选择后能形成的最大连通水田块的情况后再实施改造。请针对网格中的每个格子输出结果:若该格子原本是水田,输出 0 ;若原本是旱田,输出将该位置改造成水田后,包含该位置的最大连通水田块的大小。
开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写