首页 > 试题广场 >

数水坑

[编程题]数水坑

热度指数：1979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

${\hspace{15pt}}$ 由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个 $N\times M$ 的矩形网格，每个格子要么是水 `W`，要么是干地 `.`。
${\hspace{15pt}}$ 若两个水格子在 八连通 （上下左右及四条对角线）意义下互达，则它们属于同一个水坑。
${\hspace{15pt}}$ 给出田地示意图，计算水坑数量。

输入描述:

第一行输入两个整数 。
接下来  行，每行  个字符组成的字符串，字符集为 `W` 与 `.`，中间无空格。

输出描述:

输出一行一个整数，即水坑的数量。

示例1

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

说明

共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。

算法知识视频讲解

JavaScript Node

xuwzen

dfs标记水坑范围

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        const [N, M] = line.split(' ').map(Number);
        const mtx = Array(N);

        for (let i = 0; i < N; i++) {
            mtx[i] = (await readline()).split('');
        }

        const visited = Array.from({length: N}, () => Array(M).fill(false));
        const dfs = function(i, j) {
            if (i < 0 || i >= N || j < 0 || j >= M || visited[i][j] || mtx[i][j] === '.') return;
            visited[i][j] = true;

            dfs(i - 1, j); // 上
            dfs(i + 1, j); // 下
            dfs(i, j - 1); // 左
            dfs(i, j + 1); // 右
            dfs(i - 1, j - 1); // 左上
            dfs(i - 1, j + 1); // 右上
            dfs(i + 1, j - 1); // 左下
            dfs(i + 1, j + 1); // 右下
        };

        let count = 0;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (mtx[i][j] === '.' || visited[i][j]) continue;
                dfs(i, j);
                count++;
            }
        }
        
        console.log(count);
    }
}()

发表于 2025-09-26 13:38:14 回复(0)