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