65分求调
查看原帖
65分求调
678221
Rtaaa楼主2025/7/23 20:32
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,a[N][N],zero[N][N],book[N][N],startx,starty,startflag,tot;//zero[i][j]是0则为1
int dx[9]={0,-1,-1,-1,0,0,1,1,1},dy[9]={0,0,1,-1,-1,1,0,-1,1};
void dfs(int x,int y){
	if(x<=0||y<=0||x>n||y>m)return;//edge
	if(a[x][y]==1||book[x][y]==1)return;//judge
	book[x][y]=1;
	if(!zero[x][y]){
		bool flag=0;
		for(int i=1;i<=8;i++){
			if(zero[x+dx[i]][y+dy[i]])flag=1;
		}
		if(flag==0){
			tot++;
		}
	}
	for(int i=1;i<=8;i++){
		dfs(x+dx[i],y+dy[i]);
	}
}
void judge(int x,int y){
	if(x<=0||y<=0||x>n||y>m)return;
	if(zero[x][y]==0)return;
	zero[x][y]=0;//fill
	for(int i=1;i<=8;i++){
		judge(x+dx[i],y+dy[i]);
	}
}
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]==1)book[i][j]=1;
			if(a[i][j]==0&&startflag==0){
				startx=i,starty=j,startflag=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=1&&a[i+1][j]!=1&&a[i-1][j]!=1&&a[i][j+1]!=1&&a[i][j-1]!=1&&a[i-1][j-1]!=1&&a[i-1][j+1]!=1&&a[i+1][j-1]!=1&&a[i+1][j+1]!=1){
				zero[i][j]=1;
			}
		}
	}
	//判断有数字的格子是否需要点击 
	dfs(startx,starty);
	//判断连通块 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(zero[i][j]==1){
				tot++;
				judge(i,j);
			}
		}
	}
	cout<<tot;
}
2025/7/23 20:32
加载中...