首页 > 试题广场 >

数水坑

[编程题]数水坑

热度指数：2903 时间限制：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.

输出

说明

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

算法知识视频讲解

牛客568956019号

发表于 2025-08-14 18:32:21

n,m = input().split(" ") n,m = int(n),int(m) matrix = [] for i in range(n): a = list(input()) matrix.append(a) count = 0 visited = 展开全文

N_zip

发表于 2025-07-16 09:51:32

#include <bits/stdc++.h> using namespace std; char a[110][110]; int n, m; int ans = 0; // 用于记录水坑数量 int dx[] = {0, 0, 1, -1, -1, 1, -1, 1}; int 展开全文

ikun_ac

发表于 2025-08-08 22:12:33

题目链接数水坑题目描述给定一个的矩形网格，网格中的每个格子要么是水 W，要么是干地 .。若两个水格子在八连通（上下左右及四个对角方向）意义下互达，则属于同一个水坑。请计算水坑的数量。输入：第一行两个整数、接下来行，每行一个长度为的仅包含 W 与 . 的字符串输出：展开全文

牛客452205256号

发表于 2026-02-13 16:28:51

import sys from collections import deque data = sys.stdin.read().strip().split() it = iter(data) n = int(next(it)) m = int(next(it)) grid = [] for i 展开全文

饥饿的中国人offer多多

发表于 2025-08-07 19:29:04

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static int n, m; // 记录地图 public static char[][ 展开全文

lahm66

发表于 2025-10-09 10:18:35

dfs import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void dfs(char[][] chs,int i,int j){ 展开全文

丨阿伟丨

发表于 2025-08-29 10:27:53

题目链接数水坑题目描述由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个的矩形网格，每个格子要么是水 (W)，要么是干地 (.)。若两个水格子在八连通（上下左右及四条对角线）意义下互达，则它们属于同一个水坑。给出田地示意图，计算水坑数量。解题思路这是一个在二维网格中统计连通块数量展开全文

立花泷之介

发表于 2026-03-10 21:26:38

这道题实际上还是前一道题为核心，也就是利用BFS。本题思路是利用双重for循环遍历整个n*m田地，找到未被遍历过的水格子，作为走迷宫的“起点”。因为这是靠外循环找到的未被遍历的水格子，所以肯定是形成新水坑，那么水坑数量+1。然后把起点塞入队列，弹出队首元素，检查它八连通区域有没有其他未被遍历的水格子展开全文

讲文明的小刺猬向光而行

发表于 2026-03-10 23:08:12

#include <stdio.h> #define MAXN 105 char g[MAXN][MAXN]; int v[MAXN][MAXN]; int dx[8] = {0, 0, 1, -1, 1, -1, -1, 1}; int dy[8] = {-1, 1, 0, 0, 展开全文

Bobby兔

发表于 2025-08-18 09:29:20

import sys N, M = map(int, input().split()) visited = [] for _ in range(N): row = input() visit_row = [False if s == 'W' else True for 展开全文

问题信息

dfs

难度：

7条回答 53收藏 737浏览

数水坑

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题