当前位置：首页 > ops >正文

【题解-Acwing】1097. 池塘计数

ops 2025/6/23 19:07:50

题目：1097. 池塘计数

题目描述

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式

输出一个整数，表示池塘数目。

数据范围

1 ≤ N,M ≤ 1000

时空限制

1s / 64MB

输入样例

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<iostream>using namespace std;typedef pair<int, int> PII;
const int MaxN = 1000 + 10, MaxM = 1000 + 10;int N, M, hh, tt = -1, vis[MaxN][MaxM], sum;
char map[MaxN][MaxM];
PII q[MaxN * MaxM];void init(){hh = 0, tt = -1;
}void insert(int x, int y){q[++ tt] = {x, y};
}void dele(){hh ++;
}bool isempty(){return hh > tt;
}void bfs(int x, int y){init();insert(x, y);vis[x][y] = 1;while(!isempty()){auto t = q[hh];dele();for(int i = t.first - 1; i <= t.first + 1; i ++){for(int j = t.second - 1; j <= t.second + 1; j ++){if(i == t.first && j == t.second){continue;}if(i < 0 || i >= N || j < 0 || j >= M){continue;}if(map[i][j] == '.' || vis[i][j]){continue;}insert(i, j);vis[i][j] = 1;}}}
}int main(){scanf("%d%d", &N, &M);for(int i = 0; i < N; i ++){scanf("%s", map[i]);}for(int i = 0; i < N; i ++){for(int j = 0; j < M; j ++){if(map[i][j] == 'W' && !vis[i][j]){bfs(i, j);sum ++;}}}printf("%d", sum);return 0;
}