站外题求助
  • 板块灌水区
  • 楼主xiexiuqi29
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/8 14:46
  • 上次更新2024/6/8 18:28:23
查看原帖
站外题求助
1124770
xiexiuqi29楼主2024/6/8 14:46

【题目描述】 小实意外获得了一块荒地,于是他决定开垦它。

已知荒地是一块 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;
 } 
2024/6/8 14:46
加载中...