题目链接

数水坑

题目描述

给定一个 的矩形网格，网格中的每个格子要么是水 W，要么是干地 .。若两个水格子在八连通（上下左右及四个对角方向）意义下互达，则属于同一个水坑。请计算水坑的数量。

输入：

  • 第一行两个整数 、
  • 接下来 行，每行一个长度为 的仅包含 W 与 . 的字符串

输出：

  • 一行一个整数，表示水坑的数量

解题思路

本质是统计字符为 W 的连通块数量（八连通）。

  • 枚举每个格子：当遇到未访问的 W，水坑数加一；随后以该格子为起点进行一次泛洪（BFS/DFS）将其所在连通块的所有 W 标记为已访问。
  • 八个方向为 。
  • 访问时需判越界与字符判断，仅扩展到值为 W 且未访问过的格子。

实现要点：

  • 使用访问数组避免重复统计。
  • 代码中采用 BFS（队列）实现，避免过深递归导致的栈风险。

代码

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

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

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

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

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

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'W' && !vis[i][j]) {
                ++ponds;
                vis[i][j] = 1;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                    pair<int,int> cur = q.front();
                    q.pop();
                    int x = cur.first, y = cur.second;
                    for (int d = 0; d < 8; ++d) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (vis[nx][ny]) continue;
                        if (grid[nx][ny] != 'W') continue;
                        vis[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }

    cout << ponds << "\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();
        int m = sc.nextInt();
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            grid[i] = s.toCharArray();
        }

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

        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'W' && !vis[i][j]) {
                    ponds++;
                    vis[i][j] = true;
                    q.add(new int[]{i, j});
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        for (int d = 0; d < 8; d++) {
                            int nx = x + dx[d];
                            int ny = y + dy[d];
                            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                            if (vis[nx][ny]) continue;
                            if (grid[nx][ny] != 'W') continue;
                            vis[nx][ny] = true;
                            q.add(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
        System.out.println(ponds);
    }
}

from collections import deque

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

ponds = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'W' and not vis[i][j]:
            ponds += 1
            vis[i][j] = True
            q = deque([(i, j)])
            while q:
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and grid[nx][ny] == 'W':
                        vis[nx][ny] = True
                        q.append((nx, ny))

print(ponds)

算法及复杂度

  • 算法：BFS/DFS 泛洪计数八连通连通块
  • 时间复杂度：
  • 空间复杂度：（访问数组与队列在最坏情况下为同量级）