题目原文

描述
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.
输入
* 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.
  输出
• Line 1: The number of ponds in Farmer John’s field.
  样例输入
  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
  提示
  OUTPUT DETAILS:
  There are three ponds: one in the upper left, one in the lower left,and one along the right side.

题目翻译

描述

由于最近下雨,水汇集在农民约翰的领地各处,这是由一个矩形的N x M(1 < = N < = 100;1 < = M < = 100)矩阵。每个矩阵包含水(’ W ‘)或陆地(’ . ‘)。农民约翰想算出有多少池塘形成在他的领域。与一个水池再8个方向连接的被看作是一个池塘。
给定一个农民约翰领地的地图,求出有多少池塘。

输入

第一行:两个空格分隔的整数:N和M
第二行到N + 1行:M每行字符代表一行的农民约翰的领域。每个字符’ W ‘或’。’。字符与字符之间没有空格。

输出

第1行:池塘的数量

实现

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int head=0,tail=1,q,nextx,nexty,n,m,startx,starty,cont;
int a[100005],b[100005],x[8]={
   0,1,1,1,0,-1,-1,-1},y[8]={
   1,1,0,-1,-1,-1,0,1},c;
char map[105][105];
bool t[105][105];
bool chek(int qx,int qy)
{if(qx<=n-1&&qy<=m-1&&qx>=0&&qy>=0)return 1;return 0;
}
void dfs()
{memset(b,0,sizeof(b));memset(a,0,sizeof(a));a[1]=startx;b[1]=starty;t[startx][starty]=1;head=0;tail=1;while(head!=tail){head++;for(int i=0;i<=7;i++){nextx=a[head]+x[i];nexty=b[head]+y[i]; if(!t[nextx][nexty]&&map[nextx][nexty]=='W'&&chek(nextx,nexty)){t[nextx][nexty]=1;tail++;map[nextx][nexty]='#';a[tail]=nextx;b[tail]=nexty;}}}
}
int main()
{c=0;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'){startx=i;starty=j;map[i][j]='#';cont++;dfs();}printf("%d\n",cont);
}