题解 | #没挡住洪水#

题目链接

题目描述

给定一个 $N \times N$ 的地图，其中 . 代表洪水区域，# 代表空地。四连通的 # 组成一个独立的空地区域。在一天后，所有与洪水区域 . 相邻（上下左右）的空地 # 都会被洪水淹没。

任务是计算一天后，有多少个独立的空地区域会被完全淹没。

解题思路

本题的目标是统计被完全淹没的空地区域数量。我们首先需要明确一个区域被“完全淹没”的条件。

根据题意，一个空地格子 '#' 如果与任意一个洪水格子 '.' 相邻，那么它在一天后就会被淹没。因此，一个由多个 '#' 组成的区域会被完全淹没，当且仅当该区域内的每一个 '#' 格子都至少与一个 '.' 格子相邻。

反向思考，一个区域不会被完全淹没的条件是，该区域内存在至少一个 '#' 格子，它的所有四个邻居（上、下、左、右）也都是 '#' 格子。这样的格子我们称之为“安全格”或“内部格”，因为它不与任何洪水直接相邻，一天后不会被淹没。

因此，算法的核心思路如下：

遍历地图：我们需要找到地图上所有独立的空地区域。这可以通过图的遍历算法（如广度优先搜索 BFS 或深度优先搜索 DFS）来实现。我们使用一个 visited 数组来记录已经访问过的格子，防止重复处理。
识别与检查区域：
- 从上到下，从左到右遍历地图的每一个格子。
- 如果遇到一个尚未访问过的 '#' 格子，说明我们发现了一个新的、独立的空地区域。
- 从这个格子开始，进行一次完整的 BFS 或 DFS，以找出这个区域包含的所有格子，并将它们标记为已访问。
判断区域是否安全：
- 在对一个区域进行遍历（BFS/DFS）的过程中，我们需要同时检查该区域是否包含至少一个“安全格”。
- 为此，我们设立一个布尔标记，例如 is_safe_area，初始值为 false。
- 在遍历区域内的每一个格子 (r, c) 时，我们检查它的四个邻居。如果 (r, c) 的所有邻居都是 '#'，那么它就是一个“安全格”。
- 一旦我们在这个区域内找到了任何一个“安全格”，就可以立即将 is_safe_area 标记为 true。
计数：
- 当一个区域的完整遍历结束后，我们检查 is_safe_area 标记。
- 如果 is_safe_area 仍然为 false，说明我们遍历了整个区域都没有找到任何“安全格”。这意味着该区域的所有格子都与洪水相邻，因此该区域会被完全淹没。我们将最终计数加一。
- 如果 is_safe_area 为 true，则该区域不会被完全淹没，我们不做任何操作。
重复：继续遍历地图，直到所有格子都被访问过。最终得到的计数就是答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int n;
vector<string> grid;
vector<vector<bool>> visited;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

bool is_safe_cell(int r, int c) {
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        // 题目保证边界都是 '.', 所以不需要检查越界
        if (grid[nr][nc] == '.') {
            return false;
        }
    }
    return true;
}

void bfs(int r, int c, bool& is_safe_area) {
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        int curr_r = curr.first;
        int curr_c = curr.second;

        // 如果该区域还没被标记为安全，则检查当前格子
        if (!is_safe_area && is_safe_cell(curr_r, curr_c)) {
            is_safe_area = true;
        }

        for (int i = 0; i < 4; ++i) {
            int nr = curr_r + dr[i];
            int nc = curr_c + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                grid[nr][nc] == '#' && !visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    grid.resize(n);
    visited.assign(n, vector<bool>(n, false));

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    int submerged_count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '#' && !visited[i][j]) {
                bool is_safe_area = false;
                bfs(i, j, is_safe_area);
                if (!is_safe_area) {
                    submerged_count++;
                }
            }
        }
    }

    cout << submerged_count << endl;

    return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static char[][] grid;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    private static boolean isSafeCell(int r, int c) {
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            // 题目保证边界都是 '.', 所以不需要检查越界
            if (grid[nr][nc] == '.') {
                return false;
            }
        }
        return true;
    }

    private static boolean bfs(int r, int c) {
        boolean isSafeArea = false;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c});
        visited[r][c] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int currR = curr[0];
            int currC = curr[1];

            if (!isSafeArea && isSafeCell(currR, currC)) {
                isSafeArea = true;
            }

            for (int i = 0; i < 4; i++) {
                int nr = currR + dr[i];
                int nc = currC + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                    grid[nr][nc] == '#' && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return isSafeArea;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        grid = new char[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }

        int submergedCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '#' && !visited[i][j]) {
                    if (!bfs(i, j)) {
                        submergedCount++;
                    }
                }
            }
        }
        System.out.println(submergedCount);
    }
}

import sys
from collections import deque

def main():
    n = int(sys.stdin.readline())
    grid = [sys.stdin.readline().strip() for _ in range(n)]
    visited = [[False] * n for _ in range(n)]
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    def is_safe_cell(r, c):
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            # 题目保证边界都是 '.', 所以不需要检查越界
            if grid[nr][nc] == '.':
                return False
        return True

    def bfs(r, c):
        is_safe_area = False
        q = deque([(r, c)])
        visited[r][c] = True

        while q:
            curr_r, curr_c = q.popleft()

            if not is_safe_area and is_safe_cell(curr_r, curr_c):
                is_safe_area = True

            for i in range(4):
                nr, nc = curr_r + dr[i], curr_c + dc[i]
                if 0 <= nr < n and 0 <= nc < n and \
                   grid[nr][nc] == '#' and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc))
        
        return is_safe_area

    submerged_count = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '#' and not visited[i][j]:
                if not bfs(i, j):
                    submerged_count += 1
    
    print(submerged_count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：广度优先搜索 (BFS) / 图的遍历
时间复杂度：我们需要遍历整个 $N \times N$ 的网格。每个格子最多被访问一次（在主循环中检查）并入队一次（在BFS中）。在BFS中，我们还会检查每个格子的四个邻居。因此，总的时间复杂度与格子数成正比，为 $\mathcal{O}(N^2)$ 。
空间复杂度：visited 数组需要 $\mathcal{O}(N^2)$ 的空间。BFS的队列在最坏情况下（例如，一个螺旋形的区域）也可能存储 $\mathcal{O}(N^2)$ 个格子。因此，总空间复杂度为 $\mathcal{O}(N^2)$ 。