1097. 池塘计数
农夫约翰有一片 <span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mi">N<span id="MathJax-Span-4" class="mo">∗<span id="MathJax-Span-5" class="mi">MN∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
输入格式
第一行包含两个整数 NN 和 MM。
接下来 NN 行，每行包含 MM 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。
输出格式
输出一个整数，表示池塘数目。
数据范围
1≤N,M≤10001≤N,M≤1000
输入样例：
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>
#define fi first
#define se second
using namespace std;
const int N=1010;
const int M=N*N;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<LL,LL>PLL;
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b) {return a/gcd(a,b)*b;}
LL lowbit(LL a){return a&-a;}
//8个方向的和4个方向的是不同的计算方法
//typedf属于类型替代
//define 属于名字替代
int n,m,cnt;
char str[N][N];
void BFS(int i,int j)
{//宽搜了
PII q[M];
int l=0,r=-1;
q[++r]={i,j};
str[i][j]='*';
while(l<=r)//小于等于
{
PII x=q[l++];
for(int i=x.fi-1;i<=x.fi+1;i++)
for(int j=x.se-1;j<=x.se+1;j++)
if(i<=n&&i>0&&j<=m&&j>0&&str[i][j]=='W')
q[++r]={i,j},str[i][j]='*';
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",str[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(str[i][j]=='W')
BFS(i,j),cnt++;
}
}
cout<<cnt;
return 0;
}
定义在全局变量：
答案正确：
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1010;
const int M=N*N;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
typedef pair<LL,LL>PLL;
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b) {return a/gcd(a,b)*b;}
LL lowbit(LL a){return a&-a;}
//8个方向的和4个方向的是不同的计算方法
//typedf属于类型替代
//define 属于名字替代
int n,m,cnt;
char str[N][N];
PII q[M];
void BFS(int i,int j)
{//宽搜了
int l=0,r=-1;
q[++r]={i,j};
str[i][j]='*';
while(l<=r)//小于等于
{
PII x=q[l++];
for(int i=x.fi-1;i<=x.fi+1;i++)
for(int j=x.se-1;j<=x.se+1;j++)
if(i<=n&&i>0&&j<=m&&j>0&&str[i][j]=='W')
q[++r]={i,j},str[i][j]='*';
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",str[i]+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(str[i][j]=='W')
BFS(i,j),cnt++;
}
}
cout<<cnt;
return 0;
}