题目描述

农夫约翰的农场可以表示成 N × M 个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（'W'）或者没有积水（'.'）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的八个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。

输入格式

第 1 行：由空格隔开的两个整数：N 和 M

第 2..N+1 行：每行 M 个字符代表约翰农场的一排方格的状态。每个字符或者是 'W' 或者是 '.' ，字符之间没有空格。

数据范围

1 ≤ N,M ≤ 100

输出格式

输出只有 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.

3

完善程序

#include<bits/stdc++.h>
using namespace std;
struct Point
{
	int x,y;
	__填空(1)__ (int m_x,int m_y){
		__填空(2)__;
		__填空(3)__;
	};
	__填空(1)__ Point(){};
};
int diff[8][2] = {{1,0},{-1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
int n,m;
queue <Point> q;
string v[101];
bool flag[101][101],Found;
void bfs()
{
	Point t;
	int xx,yy,k;
	while(q.size()>0){
		t = q.front();
		q.pop();
		for(k=0;k<8;k++){
			if(Found) return;
			xx = t.x + diff[k][0];
			yy = t.y + diff[k][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]=='W'&&!flag[xx][yy] ){
				flag[xx][yy] = true;
				q.push(__填空(4)__);
			}
		}
	}
} 
int main()
{
	cin>>n>>m;
	int i,j,ans=0;
	for(i=1;i<=n;i++)
	{
		cin>>v[i];
		v[i] = "0"+ v[i];
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(v[i][j]=='W'&&!flag[i][j]){
				flag[i][j] = true;
				q.push(__填空(5)__);
				ans++;
				bfs();				
			}
		}
	}
	
	printf("%d",ans);
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}