题目描述
有 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;
}