解题思路

把所有原本是水田的格子看成无向图中的点，上下左右相邻就连边。题目本质上是：

• 先求出每个水田连通块的大小
• 再枚举每个旱田格子，假设把它变成水田，它能把周围哪些连通块连起来

这是一道标准的“网格连通块 + 合并相邻连通块”问题，核心算法是：

题目内容

某地区有一片 $n×m$ 的农田网格，每个格子要么是 “旱田”（用 $x$ 表示，无法通水），要么是 “水田”（用 $o$ 表示，可以通水）。水利部门计划对部分旱田进行改造，他们只能选择其中一块旱田，将其改造成水田。 水利部门定义 “连通水田块” 指的是四连通区域（即区域内的任意两块水田可通过上下左右移动仅经过区域内的水田互相到达），“最大连通水田块” 是指该区域在所有可能的连通水田块中面积最大（格子数量最多）。 水利部门希望先计算出不同选择后能形成的最大连通水田块的情况后再实施改造。请针对网格中的每个格子输出结果： 若该格子原本是水田，输出 $0$； 若原本是旱田，输出将该位置改造成水田后，包含该位置的最大连通水田块的大小。

输入描述

第一行包含两个正整数 $n$ 和 $m$，表示农田网格的行数和列数。接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，字符串由 $x$（旱田）和 $o$（水田）组成，描述农田网格的初始状态。

数据范围

$1 ≤ n, m ≤ 500$

输出描述

输出 $n$ 行，每行 $m$ 个整数，中间用空格隔开。 对于原本是水田的格子，输出 $0$； 对于原本是旱田的格子，输出将该位置改造成水田后，包含该位置的最大连通水田块的大小。

样例1

输入

3 3
xoo
oxo
xox

输出

5 0 0
0 6 0
3 0 5

样例2

输入

6 5
ooooo
oxxoo
xxxox
oxxoo
xooxx
ooooo

输出

0 0 0 0 0
0 12 12 0 0
13 1 12 0 12
0 9 19 0 0
9 0 0 19 19
0 0 0 0 0