湖泊计数

描述

由于最近的降雨，水在农夫约翰的田地里的各个地方都聚集了，它由一个 N x M （1 <= N <= 100; 1 <= M <= 100）正方形的矩形表示。每个方块包含水（“W”）或旱地（“.”）。农夫约翰想弄清楚他的田地里形成了多少个池塘。池塘是一组相连的正方形，其中有水，其中正方形被认为与其所有八个邻居相邻。

给定农夫约翰的田地图，确定他有多少个池塘。

输入

* 第 1 行：两个空格分隔的整数：N 和 M * 第 2..N+1 行：每行 M

个字符，代表一行农夫约翰的田地。每个字符都是“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.

示例输出

#include<bits/stdc++.h>
using namespace std;
int n,m;
char f[105][105];
void dfs(int x,int y){
    f[x][y]='.';
    for(int dx = -1; dx <= 1; dx++){
        for(int dy = -1; dy <= 1; dy++){
            int nx = x + dx;
            int ny = y + dy;
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && f[nx][ny] == 'W'){
                dfs(nx,ny);
            } 
        }
    }
    return ;
}
int main(){
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin>>f[i][j];
        }
    }
    int ans=0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(f[i][j] == 'W'){
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans;
    return 0; 
}

原文链接: https://www.cnblogs.com/8023yyl/p/17045166.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/311298

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐