首页 > 试题广场 >

数水坑

[编程题]数水坑
  • 热度指数：176 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
{\hspace{15pt}}由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个 N\times M 的矩形网格，每个格子要么是水 `W`，要么是干地 `.`。
{\hspace{15pt}}若两个水格子在 八连通 （上下左右及四条对角线）意义下互达，则它们属于同一个水坑。
{\hspace{15pt}}给出田地示意图，计算水坑数量。

输入描述:
{\hspace{15pt}}第一行输入两个整数 N,M\left(1\leqq N,M\leqq 100\right)。
{\hspace{15pt}}接下来 N 行，每行 M 个字符组成的字符串，字符集为 `W` 与 `.`，中间无空格。


输出描述:
{\hspace{15pt}}输出一行一个整数，即水坑的数量。
示例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.

输出

3

说明

共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。
算法知识视频讲解
添加回答
C/C++
聪明的迪恩准备进厂头像 聪明的迪恩准备进厂
#include <array>
#include <iostream>
#include <vector>
using namespace std;
int dict[8][2]={1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1};
void dfs(int x,int y,vector<vector<bool>>& visited,const vector<string>& grid){
    if(grid[x][y]=='.'||visited[x][y]==true){
        return;
    }
    visited[x][y]=true;
    for(int i=0;i<8;i++){
        int nx=x+dict[i][0];
        int ny=y+dict[i][1];
        if(nx<0||nx>=grid.size()||ny<0||ny>=grid[0].size()){
            continue;
        }else {
            dfs(nx,ny,visited,grid);
        }
    }
}
int main() {
    int n,m,result=0;
    cin>>n>>m;
    vector<string> grid(n);
    for(int i=0;i<n;i++){
        cin>>grid[i];
    }
    vector<vector<bool>> visited(n,vector<bool>(m,false));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(visited[i][j]==false&&grid[i][j]=='W'){
                result++;
                dfs(i,j,visited,grid);
            }
        }
    }
    cout<<result;
}
// 64 位输出请用 printf("%lld")
发表于 2025-08-13 15:48:29 回复(0)
提交观点

问题信息

dfs
难度：
1条回答 32浏览

热门推荐

相关试题

数水坑

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号