题解 | #没挡住洪水#

题目链接

题目描述

给定一个 $n \cdot n$ 的字符矩阵，'.' 表示已被洪水淹没的区域，'#' 表示空地。四联通的 '#' 组成一个区域。已知四条边界均为 '.'。洪水在接下来的一天会上涨：所有与 '.' 相邻（上下左右）的 '#' 都会被淹没。问上涨后有多少个 '#' 区域会被完全淹没。

输入：

第一行一个整数 $n$
接下来 $n$ 行，每行一个长度为 $n$ 的仅包含 '.' 与 '#' 的字符串

输出：

一行一个整数，表示将被完全淹没的空地区域数量

解题思路

设初始时的 '#' 连通块为一个区域。一天后，被淹没的仅是“与 '.' 相邻”的 '#'，且淹没是一次性的（不迭代传播）。因此一个区域会被完全淹没，当且仅当该区域中不存在“内部格子”（即四个方向的相邻格子均为 '#' 的格子）。

若区域内存在某个格子四邻皆为 '#'，则该格子不与 '.' 相邻，涨水后仍为 '#'，区域不可能被完全淹没。
否则，区域内每个格子都至少与一个 '.' 相邻，涨水后该区域所有格子都会被淹没。

实现：

枚举全图，遇到未访问的 '#' 以 BFS/DFS 扩展得到一个区域；在扩展时检测是否存在“四邻皆为 '#'”的格子。
若不存在此类格子，则答案加一。
由于边界全为 '.'，边界上的 '#' 不存在，内部性判定只需常规越界判断。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

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

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

    vector<vector<int>> vis(n, vector<int>(n, 0));
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    long long ans = 0;
    queue<pair<int,int>> q;

    auto inb = [&](int x, int y){ return 0 <= x && x < n && 0 <= y && y < n; };

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == '#' && !vis[i][j]) {
                bool hasInterior = false;
                vis[i][j] = 1;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                    auto cur = q.front(); q.pop();
                    int x = cur.first, y = cur.second;
                    bool all4 = true;
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (!inb(nx, ny) || g[nx][ny] != '#') { all4 = false; }
                    }
                    if (all4) hasInterior = true;
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (inb(nx, ny) && g[nx][ny] == '#' && !vis[nx][ny]) {
                            vis[nx][ny] = 1;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
                if (!hasInterior) ++ans;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] g = new char[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            g[i] = s.toCharArray();
        }

        boolean[][] vis = new boolean[n][n];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        long ans = 0;
        ArrayDeque<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '#' && !vis[i][j]) {
                    boolean hasInterior = false;
                    vis[i][j] = true;
                    q.add(new int[]{i, j});
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        boolean all4 = true;
                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d], ny = y + dy[d];
                            if (nx < 0 || nx >= n || ny < 0 || ny >= n || g[nx][ny] != '#') {
                                all4 = false;
                            }
                        }
                        if (all4) hasInterior = true;
                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d], ny = y + dy[d];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n && g[nx][ny] == '#' && !vis[nx][ny]) {
                                vis[nx][ny] = true;
                                q.add(new int[]{nx, ny});
                            }
                        }
                    }
                    if (!hasInterior) ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

from collections import deque

n = int(input().strip())
grid = [input().strip() for _ in range(n)]
vis = [[False] * n for _ in range(n)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(n):
    for j in range(n):
        if grid[i][j] == '#' and not vis[i][j]:
            has_interior = False
            q = deque([(i, j)])
            vis[i][j] = True
            while q:
                x, y = q.popleft()
                all4 = True
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < n and 0 <= ny < n) or grid[nx][ny] != '#':
                        all4 = False
                if all4:
                    has_interior = True
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == '#' and not vis[nx][ny]:
                        vis[nx][ny] = True
                        q.append((nx, ny))
            if not has_interior:
                ans += 1

print(ans)

算法及复杂度

算法：遍历 '#' 连通块，判定是否存在“四邻皆为 '#'”的内部格；若不存在则区域将被完全淹没
时间复杂度： $\mathcal{O}(n \cdot n)$
空间复杂度： $\mathcal{O}(n \cdot n)$