思路：并查集

进行两次dfs，第一次将所有陆地归到各自的并查集中，并采用路径压缩将并查集中的所有点归到一个点上。

之后，再次进行dfs，扫描所有的海洋，统计与该海洋相邻的并查集的点的个数及该海洋点的个数，更新答案即可。

代码

Java

import java.util.*;

public class Main {
    static int n, m;
    static String[] s;
    static int[] pre, cnt;
    static boolean[][] vis;
    static Set<Integer> sett = new HashSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 读取n
        m = sc.nextInt(); // 读取m
        s = new String[n];
        for (int i = 0; i < n; ++i) {
            s[i] = sc.next(); // 读取每行字符串
        }
        
        pre = new int[n * m];
        cnt = new int[n * m];
        vis = new boolean[n][m];
        for (int i = 0; i < n * m; ++i) {
            pre[i] = i; // 初始化并查集
            cnt[i] = 1; // 初始化每个区域的大小
        }

        // 并查集的find函数
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!vis[i][j] && s[i].charAt(j) == '#') {
                    dfs(i, j, i * m + j); // 扫描每个连通块
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!vis[i][j] && s[i].charAt(j) == '.') {
                    sett.clear();
                    ans = Math.max(ans, dfs2(i, j)); // 寻找最大的空地
                }
            }
        }
        System.out.println(ans);
    }

    // 并查集的find函数
    static int find(int x) {
        if (x == pre[x]) return x;
        return pre[x] = find(pre[x]); // 路径压缩
    }

    // 深度优先搜索用于标记连通块
    static void dfs(int x, int y, int z) {
        if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || s[x].charAt(y) == '.') return;
        int tz = find(x * m + y); // 找到该格子的根
        if (tz != z) {
            pre[tz] = z; // 合并两个区域
            cnt[z] += cnt[tz]; // 更新区域大小
        }
        vis[x][y] = true; // 标记已访问
        dfs(x + 1, y, z); // 向四个方向递归
        dfs(x - 1, y, z);
        dfs(x, y + 1, z);
        dfs(x, y - 1, z);
    }

    // 第二次深度优先搜索用于计算空地的最大值
    static int dfs2(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) return 0;
        if (s[x].charAt(y) == '#') {
            int z = find(x * m + y); // 找到该格子的根
            if (sett.contains(z)) return 0; // 如果已处理过该连通块则跳过
            sett.add(z); // 添加到集合中
            return cnt[z]; // 返回该连通块的大小
        }
        if (vis[x][y]) return 0; // 如果已访问则跳过
        vis[x][y] = true; // 标记已访问
        int ret = 1; // 计数当前空地
        ret += dfs2(x + 1, y); // 向四个方向递归
        ret += dfs2(x - 1, y);
        ret += dfs2(x, y + 1);
        ret += dfs2(x, y - 1);
        return ret; // 返回总空地大小
    }
}

题目内容

米小游和小美到达了一个被红色和海洋包裹着的星球，星球上有一些陆地，小美准备点燃其中一大片海。

具体来说，就是在一张二维地图上，分成了$n×m$个格子，每个格子的类型要么是大海，要么是陆地，若相邻(通过格子的边相邻)两个格子的类型相同，则视为同一个连通块，大海被点燃后会变成陆地，点燃一片大海就是把一个 大海连通块变成一个陆地连通块。

米小游想知道在小美最多点燃一片大海后，最大陆地连通块大小的最大值是多少。

输入描述

第一行输入两个整数$n,m$($1≤n，m≤1000$)，表示地图大小。

接下来$n$行，每行输入一个长度为$m$的字符串$s$表示地图，其中'_'表示这个格子是大海，‘#’表示这个格子是陆地。

输出描述

输出一个整数表示答案

样例1

输入

5 5
##..#
#..#.
###..
.#.#.
#.#..

输出

17

说明

点燃右下角的那一片大海，可以发现，点燃其他大海后的效果没有更优。