题解 | #数水坑#

题目链接

题目描述

由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个 $N \times M$ 的矩形网格，每个格子要么是水 (W)，要么是干地 (.)。

若两个水格子在八连通（上下左右及四条对角线）意义下互达，则它们属于同一个水坑。

给出田地示意图，计算水坑数量。

解题思路

这是一个在二维网格中统计连通块数量的经典问题。核心思想是遍历整个网格，每当我们发现一个属于水坑但尚未被访问过的水格子时，就找到了一个新的水坑。然后，我们从这个格子出发，通过搜索（如深度优先搜索DFS或广度优先搜索BFS）找到并标记所有与它相连的水格子，以确保同一个水坑不会被重复计数。

1. 算法流程

初始化：
- 创建一个 visited 数组（与网格等大），用于记录哪些格子已经被访问过，所有元素初始为 false。
- 初始化水坑计数器 count = 0。
遍历网格：
- 使用双层循环遍历田地中的每一个格子，坐标为 $(i, j)$ 。
发现新水坑：
- 在循环中，检查当前格子 $(i, j)$ 是否满足两个条件：
  - 是水格子（grid[i][j] == 'W'）。
  - 尚未被访问过（visited[i][j] == false）。
- 如果同时满足，说明我们发现了一个新的、独立的水坑。此时，我们将 count 加一。
标记整个水坑：
- 从当前格子 $(i, j)$ 开始，执行一次图搜索算法（DFS或BFS），将所有与 $(i, j)$ 八连通的水格子都标记为已访问。
- 深度优先搜索 (DFS) 的实现方式：
  - 创建一个 dfs(x, y) 函数。
  - 首先，将 (x, y) 标记为已访问。
  - 然后，检查 (x, y) 的所有八个方向的邻居格子 (nx, ny)。
  - 对于每一个邻居，如果它在网格边界内、是一个水格子、且尚未被访问，就递归调用 dfs(nx, ny)。
完成计数：
- 当外层循环遍历完所有格子后，count 的值就是水坑的总数。

通过这种方式，我们确保了每个水坑只在其第一个被发现的格子那里被计数一次，随后整个水坑的所有格子都被标记，避免了重复计算。

代码

c++
java
python

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

using namespace std;

int N, M;
vector<string> grid;
vector<vector<bool>> visited;

// 八个方向的偏移量
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 检查边界
        if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
            // 如果是未访问的水格子，继续搜索
            if (grid[nx][ny] == 'W' && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    cin >> N >> M;
    grid.resize(N);
    visited.assign(N, vector<bool>(M, false));

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

    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (grid[i][j] == 'W' && !visited[i][j]) {
                count++;
                dfs(i, j);
            }
        }
    }

    cout << count << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static int N, M;
    private static char[][] grid;
    private static boolean[][] visited;
    // 八个方向的偏移量
    private static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    private static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 检查边界
            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                // 如果是未访问的水格子，继续搜索
                if (grid[nx][ny] == 'W' && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }

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

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

        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 'W' && !visited[i][j]) {
                    count++;
                    dfs(i, j);
                }
            }
        }
        System.out.println(count);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(100 * 100 + 10)

def solve():
    N, M = map(int, input().split())
    grid = [input() for _ in range(N)]
    visited = [[False for _ in range(M)] for _ in range(N)]

    # 八个方向的偏移量
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]

    def dfs(x, y):
        visited[x][y] = True
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            
            # 检查边界
            if 0 <= nx < N and 0 <= ny < M:
                # 如果是未访问的水格子，继续搜索
                if grid[nx][ny] == 'W' and not visited[nx][ny]:
                    dfs(nx, ny)

    count = 0
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'W' and not visited[i][j]:
                count += 1
                dfs(i, j)
    
    print(count)

solve()

算法及复杂度

算法：深度优先搜索 (DFS) / 广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(N \cdot M)$ 。我们对整个网格进行一次遍历。在遍历过程中，每个格子最多被访问一次（在主循环中检查）并作为DFS/BFS的起点一次。在DFS/BFS中，每个格子也只会被访问一次。因此，总的访问次数与网格大小成正比。
空间复杂度： $\mathcal{O}(N \cdot M)$ 。这主要由存储 visited 数组（或在DFS中，递归调用栈的深度）决定。在最坏的情况下（例如，一个螺旋形的水坑填满了整个网格），DFS的递归深度可能达到 $N \cdot M$ 。