上海市计算机学会竞赛平台2024年7月月赛丙组池塘计数

题目描述

有 n×mn×m 个方格，一些方格是水，用字符 . 表示，一些方格是陆地，用字符 # 表示。

两个方格相邻的定义是这两个方格至少有一个公共的边，每个方格最多有四个相邻的方格。

若相邻的方格都是水，那么就会连成更大一个池塘。请计算给定的地形中有多少个不连通的池塘。

输入格式

• 第一行：两个整数 nn 和 mm；
• 第二行到第 n+1n+1 行：第 i+1i+1 行有 mm 个字符。

输出格式

• 单个整数：表示有多少个不连通的池塘

数据范围

• 对于 30%30% 的数据，1≤n,m≤101≤n,m≤10
• 对于 60%60% 的数据，1≤n,m≤1001≤n,m≤100
• 对于 100%100% 的数据，1≤n,m≤2001≤n,m≤200

样例数据

输入:

3 5
...##
.#.##
###..

输出:

2

详见代码:

#include<bits/stdc++.h>
using namespace std;
int n, m;
char a[205][205];
int ans = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void bfs(int x, int y) 
{
    queue<pair<int, int>> q;
    q.push({x, y});
    while(!q.empty()) 
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++) 
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (a[xx][yy] == '.') 
            {
                q.push({xx, yy});
                a[xx][yy] = '#';
            }
        }
    }
    return;
}
int main() 
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            if (a[i][j] == '.') 
            {
                a[i][j] = '#';
                ans++;
                bfs(i, j);
            }
        }
    }
    cout << ans;
    return 0;
}