求助,12pt
查看原帖
求助,12pt
1262004
zhao_zi_ou楼主2025/1/11 18:47
#include <bits/stdc++.h>
using namespace std; 
#define LL long long
#define LD long double
#define UG unsigned
int n;
int s[1005][1005];
bool f[1005][1005];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void dr()
{
	memset(s,-1,sizeof(s));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			s[i][j]=(c=='.'?-1:0);
		}
	}
	for(int x=1;x<=n;x++)
	{
		for(int y=1;y<=n;y++)
		{
			if(s[x][y]!=-1)
			{
				for(int k=0;k<4;k++)
				{
					int tx=x+dx[k];
					int ty=y+dy[k];
					if(s[tx][ty]==-1) s[x][y]=1;
				}
			}
		}
	}
}
bool bfs(int stx,int sty)
{
	bool flag=true;
	queue<pair<int,int>> q;
	q.push(make_pair(stx,sty));
	f[stx][sty]=true;
	if(s[stx][sty]==1) return false;
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int k=0;k<4;k++)
		{
			int tx=x+dx[k];
			int ty=y+dy[k];
			if(s[tx][ty]!=-1&&!f[tx][ty])
			{
				if(s[tx][ty]==0) flag=false;
				q.push(make_pair(tx,ty));
				f[tx][ty]=true;
				s[tx][ty]=-1;
			}
		}
	}
	return flag;
}
int main()
{
	dr();
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(s[i][j]!=-1) ans+=int(bfs(i,j));
		}
	}
	cout<<ans;
	return 0;
}

/*

至理名言
 
骗分过样例,暴力出奇迹。
暴搜挂着机,打表出省一。
N方过百万,暴力踩标算。
肥修赛大象,只是代码短。

想要骗到分,一定有方法。
图论背模版,数论背公式。
动规背方程,高精背代码。
要是都不会,干脆输样例。

模拟只会猜题意,贪心只能过样例。
数学上来先打表,DP一般看规律。

组合数学靠运气,计算几何瞎暴力。
图论一顿套模版,数论只会GCD。

-------------------------------

洛谷规则怪谈: 

1、岛国题输出要换行, 若特殊说明可以不换, 请忽略此条规则
2、提交代码中不会出现strign或mian, 若出现,立马改正,并扇自己3耳光
3、每天在luogu起码刷3道题, 但若是1月内抄10及以上篇题解, 后果自负

若违反以上规则, 轻则WA,重则棕名或封号

-------------------------------

next_permutation(指针1,指针2);

priority_queue<signed,vector<signed>,greater<signed>> q;

*/
2025/1/11 18:47
加载中...