首页 > 试题广场 >

数水坑

[编程题]数水坑
  • 热度指数：1970 时间限制：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

说明

共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。
算法知识视频讲解
添加回答
Java
清浅QAQ头像 清浅QAQ
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] graph = new char[n][m];
        int[][] use = new int[n][m];
        int res = 0;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            for(int j = 0; j < m; j++){
                graph[i][j] = s.charAt(j);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(graph[i][j] == 'W' && use[i][j] == 0){
                    res++;
                    dfs(graph, use, i, j, n, m);
                }
            }
        }
        System.out.println(res);
    }
    public static void dfs(char[][] graph, int[][] use, int x, int y, int n, int m){
        if(x < 0 || x >= n || y < 0 || y >= m || use[x][y] == 1 || graph[x][y] == '.')
            return;
        use[x][y] = 1;
        for(int i = x - 1; i < x + 2; i++){
            for(int j = y - 1; j < y + 2; j++){
                dfs(graph, use, i, j, n, m);
            }
        }
    }
}
发表于 2025-09-22 21:15:34 回复(0)
提交观点

问题信息

dfs
难度：
1条回答 431浏览

热门推荐

相关试题

数水坑

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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