Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 35122 Accepted: 17437 Description
Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John’s field, determine how many ponds he has. Input
- Line 1: Two space-separated integers: N and M
- Lines 2..N 1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them. Output
- Line 1: The number of ponds in Farmer John’s field. Sample Input
10 12 W……..WW. .WWW…..WWW ….WW…WW. ………WW. ………W.. ..W……W.. .W.W…..WW. W.W.W…..W. .W.W……W. ..W…….W. Sample Output
3 Hint
OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side.
我的理解是每一次BFS之后一个水洼就都被替换成’W’,当不存在’W’的时候，说明没有水洼了，那么BFS的次数就是水洼的数目，每个点只扫描一次。
代码语言：javascript复制#include<iostream>
#include<queue>
#define N 110 //比题目指定的N范围大一点
#define M 110
using namespace std;
typedef pair<int, int> point; //这个时候写pair比结构体要方便一点
int res = 0; //符合要求的水洼数目
char maze[N][M]; //记录整个地图
void BFS(int x,int y)
{
queue<point>que; //建立队列
point current; //记录当前的点的信息
int i, j, dx, dy, dir_1, dir_2;
for (i = 0; i < x; i )
{
for (j = 0; j < y; j )
{
if (maze[i][j] == 'W') //如果当前这个点是积水
{
que.push(point(i,j)); //就加入队列
maze[i][j] = '.'; //标记已经搜索过了这个点
while (!que.empty()) //判断队列是否为空
{
current = que.front(); //取出队首元素
que.pop(); //弹出第一个元素，不返回
for (dir_1 = -1; dir_1 <= 1; dir_1 ) //8个方向的遍历
{
for (dir_2 = -1; dir_2 <= 1; dir_2 )
{
dx = current.first dir_1, dy = current.second dir_2; //坐标的变化
if (dx >= 0 && dx < x&&dy >= 0 && dy < y&&maze[dx][dy] != '.') //判断是否这个点合法
{
que.push(point(dx, dy)); //合法则加入队列
maze[dx][dy] = '.'; //标记这个点已经搜索过了
}
}
}
}
res ; //水洼数目 1
}
}
}
}
void solve()
{
int k = 0, x, y;
cin >> x >> y;
for (k = 0; k < x; k )
{
cin >> maze[k];
}
BFS(x,y);
cout << res << endl;
}
int main(void)
{
solve();
return 0;
}
