60分求大牛解,已经注释思路,感激不尽
查看原帖
60分求大牛解,已经注释思路,感激不尽
288090
ZHYCDQ楼主2025/6/29 13:14
#include<bits/stdc++.h>
using namespace std;


int n,m,js,ans,maxx;
char a[1005][1005]; //图 
int x[1000050];  //记录杂物的X坐标; 
int y[1000050];	 //记录杂物的y坐标; 
int x_a[4]={1,0,0,-1};  //判定周边 
int y_a[4]={0,1,-1,0};  //判定周边 


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]=='#'){   //记录杂物 
				x[js] = i;
				y[js] = j;
				js++;     //记录杂物数量 
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i+1][j]!='#'&&a[i][j+1]!='#'&&a[i-1][j]!='#'&&a[i][j-1]!='#'&&a[i][j]!='#'){
				ans++;  //记录什么都不动时,可开垦数量。 
			}
		}
	}

	for(int kk=0;kk<js;kk++){
		a[x[kk]][y[kk]]='.';  //假设移出这块杂物 
		int lll = 0;  //统计周边能开垦的荒地,因为不移出时,周边都不能开垦; 
		for(int i=0;i<4;i++){ //四次计算,周边可开垦数量 
			int xx=x[kk]+x_a[i];
			int yy=y[kk]+y_a[i];
			if(a[xx][yy]=='.'&&a[xx][yy+1]!='#'&&a[xx+1][yy]!='#'&&a[xx-1][yy]!='#'&&a[xx][yy-1]!='#'){
				lll++;
			}
		}
		maxx = max(maxx,lll); //得到移出杂物后,腾出开垦地最多的数量 
		a[x[kk]][y[kk]]='#';	//复原这块地,去模拟下一块地 
	}
	cout<<ans+maxx+1<<endl;   //得出原本的地+移除后周边的地+加上移出的本身 
	return 0;
} 
2025/6/29 13:14
加载中...