本文共 2264 字，大约阅读时间需要 7 分钟。

在解决这个问题时，我们需要判断给定的岛屿是否会被完全淹没。根据题目描述，一个岛屿不会被淹没的条件是该岛屿上存在至少一个陆地点，其四个邻居（上下左右）都是陆地。否则，该岛屿会被淹没。

问题分析

为了确定岛屿是否会被淹没，我们可以采用深度优先搜索（DFS）来遍历每个岛屿。DFS不仅可以帮助我们标记所有属于同一岛屿的陆地点，还可以在遍历过程中检查是否存在满足条件的点。

解决思路

优化思路

• 内存优化：避免在每次递归调用时创建新的数组，而是直接在原数组上进行修改。
• 时间复杂度：确保算法的时间复杂度为O(N²)，避免因内存分配问题导致超时。

代码实现

import java.io.*;public class Main {    static int N = 1010;    static int n;    static char[][] g = new char[N][N];    static char[][] backup = new char[N][N];    static int dx[] = {-1, 0, 1, 0};    static int dy[] = {0, 1, 0, -1};    static boolean isExist;    public static void dfs(int x, int y) {        g[x][y] = '.'; // 标记为被访问过        if (check(x, y)) {            isExist = true;        }        for (int i = 0; i < 4; i++) {            int a = x + dx[i];            int b = y + dy[i];            if (a < 0 || a >= n || b < 0 || b >= n) continue;            if (g[a][b] == '.') continue;            dfs(a, b);        }    }    public static boolean check(int x, int y) {        for (int i = 0; i < 4; i++) {            int a = x + dx[i];            int b = y + dy[i];            if (a < 0 || a >= n || b < 0 || b >= n) continue;            if (backup[a][b] == '.') return false;        }        return true;    }    public static void main(String args[]) throws Exception {        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));        n = Integer.parseInt(bf.readLine());        for (int i = 0; i < n; i++) {            String s = bf.readLine();            g[i] = s.toCharArray();            backup[i] = s.toCharArray();        }        int num = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (g[i][j] == '#') {                    isExist = false;                    dfs(i, j);                    if (!isExist) {                        num++;                    }                }            }        }        System.out.println(num);    }}

代码解释

通过这种方法，我们可以高效地判断每个岛屿是否会被淹没，确保算法在合理时间内完成。