首页 > 试题广场 >

数水坑

[编程题]数水坑

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

输出

说明

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

算法知识视频讲解

代码怎么又不跑了

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static boolean[][] visited;

    private static int[][] direction = new int[][] {
        {-1, 0}, {1, 0}, {0, 1}, {0, -1},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String[] line = in.nextLine().split(" ");
            int N = Integer.parseInt(line[0]);
            int M = Integer.parseInt(line[1]);
            visited = new boolean[N][M];
            char[][] matrix = new char[N][M];
            for (int i = 0; i < N; i++) {
                matrix[i] = in.nextLine().toCharArray();
            }

            int resCount = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (matrix[i][j] == 'W' && !visited[i][j]) {
                        resCount++;
                        dfs(i, j, matrix);
                    }
                }
            }
            System.out.println(resCount);
        }
    }

    public static void dfs(int x, int y, char[][] matrix) {
        int N = matrix.length, M = matrix[0].length;
        for (int i = 0; i < direction.length; i++) {
            int dx = x + direction[i][0];
            int dy = y + direction[i][1];
            if (dx >= 0 && dx < N && dy >= 0 && dy < M && matrix[dx][dy] == 'W' && !visited[dx][dy]) {
                visited[dx][dy] = true;
                dfs(dx, dy, matrix);
            }
        }
    }
}

发表于 2025-12-08 15:20:58 回复(0)

nothing5

思想：遍历每个点，是水坑并且没有标记，数量加1，然后递归标记相邻的水坑

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//方向数组左，下，右，上，右下，左上，右上，左下
int dx[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};

void dfs(int n, int m, vector<string>& w, vector<vector<bool>>& visited, int start_X,
         int start_Y) {
    visited[start_X][start_Y] = true;

    //遍历方向
    for (int i = 0; i < 8; i ++) {
        int nx = start_X + dx[i];
        int ny = start_Y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m
        &&visited[nx][ny] == false && w[nx][ny] == 'W'){
            visited[nx][ny] = true;
            dfs(n, m, w, visited, nx, ny);
        }
    }
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<string> w(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] ;
    }

    //计数
    int count_num = 0;

    //标记访问数组
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if(w[i][j] == 'W' && !visited[i][j]) {
                count_num ++;
                dfs(N, M, w, visited, i, j);
            }
        }
    }
    cout << count_num << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-10-27 15:00:26 回复(0)

Python3

丰川小祥有点乖

n, m = map(int, input().split(" ")) # 输入矩阵大小

map = [] # 定义地图

for _ in range(n): # 输入地图
    map.append(input().strip())

flag = [[False] * m for _ in range(n)] # 建立标记矩阵，等遇见一个水坑就打上一个标记
dirs = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] # 8个方向

num = 0 # 水坑数量

def dfs(x,y): # 每遇见一个水坑，就通过dfs把连通的所有水坑标记
    
    for dx, dy in dirs: # 循环尝试往8个方向移动
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m and map[nx][ny] == "W" and not flag[nx][ny]: # 符合条件说明是水坑，打上标记
            flag[nx][ny] = True
            dfs(nx,ny)
    


for i in range(n): # 循环整个地图，遇见一个没打标记的水坑，就用dfs把所有水坑标记合成一个水塘，然后水塘数+1
    for j in range(m):
        if map[i][j] == "W" and not flag[i][j]:
            dfs(i,j)
            num += 1

print(num)

发表于 2025-10-13 18:54:36 回复(0)

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)

Java

清浅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)

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

难度：

6条回答 34收藏 425浏览

数水坑

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题