社区讨论

dfs 36分求助

P8662[蓝桥杯 2018 省 AB] 全球变暖参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo3d4awy
此快照首次捕获于
2023/10/24 04:40
2 年前
此快照最后确认于
2023/10/24 04:40
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
typedef long double onr;
#define fr(y) for(inr i=1;i<=y;i++)
int n,a[1007][1007],b[1007][1007],ca=0,cb=0,via[1007][1007],vib[1007][1007];
char ch;
int dx[]= {0,1,-1,0, 0};
int dy[]= {0,0, 0,1,-1};
inline void dfsa(int x,int y) {
	if(via[x][y]==0) ca++,via[x][y]=1;
	fr(4) {
		int tx=x+dx[i],ty=y+dy[i];
		if(a[tx][ty]==1&&1<tx&&tx<n&&1<ty&&ty<n&&!via[tx][ty]) {
			via[tx][ty]=1;
			dfsa(tx,ty);
		}
	}
}
inline void dfsb(int x,int y) {
	if(vib[x][y]==0) cb++,vib[x][y]=1;
	fr(4) {
		int tx=x+dx[i],ty=y+dy[i];
		if(b[tx][ty]==1&&1<tx&&tx<n&&1<ty&&ty<n&&!vib[tx][ty]) {
			vib[tx][ty]=1;
			dfsb(tx,ty);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n;
	fr(n)
	for(int j=1; j<=n; j++) {
		cin>>ch;
		if(ch=='#') a[i][j]=1;
	}
	fr(n)
	for(int j=1; j<=n; j++)
		if(a[i][j]&&via[i][j]==0)
			dfsa(i,j);
	/*
	fr(n) {
		for(int j=1; j<=n; j++) cout<<via[i][j]<<" ";
		cout<<endl;
	}//*/
	fr(n)
	for(int j=1; j<=n; j++)
		if(a[i][j]==1)
			if(a[i-1][j]==1&&a[i+1][j]==1&&a[i][j-1]==1&&a[i][j+1]==1)
				b[i][j]=1;
	fr(n)
	for(int j=1; j<=n; j++)
		if(b[i][j]&&vib[i][j]==0)
			dfsb(i,j);
	/*
	fr(n) {
		for(int j=1; j<=n; j++) cout<<vib[i][j]<<" ";
		cout<<endl;
	}//*/
	cout<<ca-cb<<endl;
	return 0;
}
思路是先求一遍岛屿数再在淹后再求一遍岛屿数相减

回复

3 条回复,欢迎继续交流。

正在加载回复...