【题目描述】 小实意外获得了一块荒地,于是他决定开垦它。
已知荒地是一块 N×N 的正方形区域,荒地中布满了灌木丛,当然也有空地。小实决定将里面的灌木丛全部清除。为了获取荒地内的全貌,小实借助无人机拍摄了荒地的正上方照片。为了方便查看,他将有灌木丛的地方用 # 表示,空地用 . 表示。
小实清理灌木丛的方式是这样的:他只能站在空地的位置上,然后去清理与空地相邻的灌木丛。并且小实不会在当天走到刚清理完的灌木丛的位置上(因为太脏了)。
小实将相连(上下左右)的灌木丛看成一个块。例如对于一个 5∗5的空地,有两块灌木丛:
....#
.###.
.###.
.###.
.....
经过第一天的清理后,就会变成:
.....
.....
..#..
.....
.....
现在小实想知道,经过第一天的清理后,有多少块会被完全清理掉。一个块被完全清理掉需要满足的条件为块中所有的灌木丛都被清理。
【输入格式】 第一行输入一个整数 N
接下来输入一个 N×N 的字符矩阵,代表拍摄下来的照片。# 表示灌木丛,. 表示空地。
【输出格式】 输出一个数,表示经过第一天后,有多少块会被完全清理。
【输入样例】 5
..###
#.###
.....
..##.
.##..
【输出样例】 2 【样例解释】 样例中共有 3 3 个块,其中下方和左上方的块会被完全清理。
【数据范围】 1 ≤ ≤ 1000 1≤N≤1000
为什么代码全WA
#include<bits/stdc++.h>
using namespace std;
int n,a[1002][1002],b[1002][1002],k1,k2;
int main()
{
cin>>n;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
a[i][j]=b[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
char s;
cin>>s;
if(s=='.')
a[i][j]=0,b[i][j]=0;
if(s=='#')
a[i][j]=1,b[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]&&(!a[i+1][j]&&!a[i][j+1]&&a[i-1][j]))
k1++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j])
if(!b[i-1][j]||!b[i][j-1]||!b[i+1][j]||!b[i][j+1])
a[i][j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]&&(!a[i+1][j]&&!a[i][j+1]&&a[i-1][j]))
k2++;
}
cout<<k1-k2;
return 0;
}