解题思路

• 将原始网格中所有水田 'o' 按四方向（上、下、左、右）进行连通块划分，给每个水田格子分配一个组件编号，并记录每个组件的面积（格子数）。可用 BFS/DFS 完成，推荐 BFS 防止递归过深。

• 对于每一个格子：

  • 若原本是水田 'o'，答案为 0（题意要求）。
  • 若原本是旱田 'x'，把它视作改造成水田后，它会与其四邻中至多四个水田组件相连。取这些相邻组件编号的去重集合，把对应面积求和，再加上当前格子本身的 1，即为“将该位置改造成水田后，包含该位置的最大连通水田块大小”。

• 这样即可一次预处理、一次扫描得到所有答案。

核心要点：

1. 先用 BFS 标号所有 'o' 连通块并记录大小。
2. 对每个 'x'，用集合去重相邻的组件编号，大小为 1 + sum(size[id] for id in uniq_neighbors)。

复杂度分析

• 连通块标号：每个格子仅入队出队一次，时间 O(n·m)，空间 O(n·m) 存储编号与队列。
• 逐格计算答案：每格最多查看 4 个邻居，时间 O(n·m)，空间为常数级额外集合。
• 总体时间 O(n·m)，空间 O(n·m)，满足 n,m ≤ 500 的数据范围。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
from collections import deque

# 外部函数：计算答案矩阵
def solve_grid(n, m, grid):
    # 组件编号，-1 表示非水田
    comp_id = [[-1] * m for _ in range(n)]
    sizes = []  # 各组件大小
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]

    # BFS 标号所有水田连通块
    cid = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'o' and comp_id[i][j] == -1:
                q = deque()
                q.append((i, j))
                comp_id[i][j] = cid
                cnt = 1
                while q:
                    x, y = q.popleft()
                    for dx, dy in dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < m:
                            if grid[nx][ny] == 'o' and comp_id[nx][ny] == -1:
                                comp_id[nx][ny] = cid
                                cnt += 1
                                q.append((nx, ny))
                sizes.append(cnt)
                cid += 1

    # 计算答案
    ans = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'x':
                seen = set()
                add = 1  # 把当前格子改成水田
                for dx, dy in dirs:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < n and 0 <= ny < m and comp_id[nx][ny] != -1:
                        seen.add(comp_id[nx][ny])
                for k in seen:
                    add += sizes[k]
                ans[i][j] = add
            else:
                ans[i][j] = 0
    return ans

# 主函数：读入与输出（ACM 风格）
def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    grid = [list(next(it).strip()) for _ in range(n)]
    res = solve_grid(n, m, grid)
    out_lines = []
    for i in range(n):
        out_lines.append(" ".join(str(res[i][j]) for j in range(m)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名固定为 Main
import java.io.*;
import java.util.*;

public class Main {
    // 外部函数：计算答案矩阵
    static int[][] solveGrid(int n, int m, char[][] g) {
        int[][] comp = new int[n][m]; // 组件编号
        for (int i = 0; i < n; i++) Arrays.fill(comp[i], -1);
        ArrayList<Integer> sizes = new ArrayList<>();
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

        int cid = 0;
        // BFS 标号
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'o' && comp[i][j] == -1) {
                    comp[i][j] = cid;
                    q.add(new int[]{i, j});
                    int cnt = 1;
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        for (int[] d : dirs) {
                            int nx = x + d[0], ny = y + d[1];
                            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                                if (g[nx][ny] == 'o' && comp[nx][ny] == -1) {
                                    comp[nx][ny] = cid;
                                    cnt++;
                                    q.add(new int[]{nx, ny});
                                }
                            }
                        }
                    }
                    sizes.add(cnt);
                    cid++;
                }
            }
        }

        // 计算答案
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'x') {
                    // 使用 HashSet 去重相邻组件
                    HashSet<Integer> set = new HashSet<>();
                    for (int[] d : dirs) {
                        int nx = i + d[0], ny = j + d[1];
                        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                            if (comp[nx][ny] != -1) set.add(comp[nx][ny]);
                        }
                    }
                    int sum = 1; // 当前格子改成水田
                    for (int id : set) sum += sizes.get(id);
                    ans[i][j] = sum;
                } else {
                    ans[i][j] = 0;
                }
            }
        }
        return ans;
    }

    // 主函数：读入与输出
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] g = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = br.readLine().trim();
            g[i] = s.toCharArray();
        }
        int[][] res = solveGrid(n, m, g);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j > 0) sb.append(' ');
                sb.append(res[i][j]);
            }
            if (i + 1 < n) sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 兼容 C++11 的实现：去掉结构化绑定与花括号 push
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> solveGrid(int n, int m, const vector<string>& g) {
    vector<vector<int>> comp(n, vector<int>(m, -1)); // 连通块编号
    vector<int> sizes;                                // 各块大小
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    queue<pair<int,int>> q;
    int cid = 0;
    // BFS 标号所有水田 'o'
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'o' && comp[i][j] == -1) {
                comp[i][j] = cid;
                q.push(std::make_pair(i, j));
                int cnt = 1;
                while (!q.empty()) {
                    pair<int,int> cur = q.front(); q.pop();
                    int x = cur.first, y = cur.second;
                    for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                            if (g[nx][ny] == 'o' && comp[nx][ny] == -1) {
                                comp[nx][ny] = cid;
                                ++cnt;
                                q.push(std::make_pair(nx, ny));
                            }
                        }
                    }
                }
                sizes.push_back(cnt);
                ++cid;
            }
        }
    }

    // 计算答案矩阵
    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'x') {
                set<int> s;                 // 相邻块去重
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                        if (comp[nx][ny] != -1) s.insert(comp[nx][ny]);
                    }
                }
                int sum = 1;                // 自身改成水田
                for (int id : s) sum += sizes[id];
                ans[i][j] = sum;
            } else {
                ans[i][j] = 0;              // 原本是水田输出 0
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    auto res = solveGrid(n, m, g);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (j) cout << ' ';
            cout << res[i][j];
        }
        if (i + 1 < n) cout << '\n';
    }
    return 0;
}

题目内容

某地区有一片 $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