50分DFS求调
查看原帖
50分DFS求调
1284088
meifan666楼主2024/7/11 13:36
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum;
bool a[1010][1010];
bool b[1010][1010];
bool c[1010][1010];//记空格
void DFS_kong(int x,int y){
	a[x][y]=1;
	b[x][y]=1;
	c[x][y]=1;
	if(x+1<=n&&!b[x+1][y]){
		DFS_kong(x+1,y);
	}
	if(x-1>0&&!b[x-1][y]){
		DFS_kong(x-1,y);
	}
	if(y+1<=n&&!b[x][y+1]){
		DFS_kong(x,y+1);
	}
	if(y-1>0&&!b[x][y-1]){
		DFS_kong(x,y-1);
	}//四联通
	if(y-1>0&&x-1>0&&!b[x-1][y-1]){
		DFS_kong(x-1,y-1);
	}
	if(y-1>0&&x+1<=n&&!b[x+1][y-1]){
		DFS_kong(x+1,y-1);
	}
	if(y+1<=n&&x-1>0&&!b[x-1][y+1]){
		DFS_kong(x-1,y+1);
	}
	if(y+1<=n&&x+1<=n&&!b[x+1][y+1]){
		DFS_kong(x+1,y+1);
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]){
				b[i+1][j]=1;
				b[i+1][j+1]=1;
				b[i+1][j-1]=1;
				b[i-1][j]=1;
				b[i-1][j+1]=1;
				b[i-1][j-1]=1;
				b[i][j+1]=1;
				b[i][j-1]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!a[i][j]){
				if(!a[i+1][j]&&!a[i-1][j]&&!a[i+1][j+1]&&!a[i-1][j+1]
					&&!a[i+1][j-1]&&!a[i-1][j-1]&&!a[i][j+1]&&!a[i][j-1]){
					sum++;
					DFS_kong(i,j);
				}
			}
		}
	}
//	cout<<sum<<'\n';
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<a[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
//	cout<<'\n'<<'\n';
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<c[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
//	cout<<'\n';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!a[i][j]&&
				!c[i+1][j]&&!c[i-1][j]&&!c[i+1][j+1]&&!c[i-1][j+1]
				&&!c[i+1][j-1]&&!c[i-1][j-1]&&!c[i][j+1]&&!c[i][j-1]){
//				printf("%d %d\n",i,j);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}
2024/7/11 13:36
加载中...