社区讨论

C++12分求助

P2919[USACO08NOV] Guarding the Farm S参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lvb0pyma
此快照首次捕获于
2024/04/22 21:53
2 年前
此快照最后确认于
2024/04/23 13:28
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int a[706][706];
bool vis[706][706];
const int dx[8]={1,-1,0,0,1,1,-1,-1};
const int dy[8]={0,0,1,-1,-1,1,1,-1};
void dfs(int x,int y,int cnt,int high){
	//当前在(x,y),要染成cnt色,能染的海拔<=high 
	for(int i = 0;i < 4;++i){
	 	int xx=x+dx[i];
	 	int yy=y+dy[i];
	 	int xz_h=a[x][y],next_h=a[xx][yy];
	 	if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]!=0){
	 		if(next_h>xz_h){
	 			high=next_h;
			 }
			 a[xx][yy]=cnt;
			 vis[xx][yy]=true;
			 dfs(xx,yy,cnt,high);
		 }
	}
	for(int i = 4;i < 8;++i){
	 	int xx=x+dx[i];
	 	int yy=y+dy[i];
	 	if(i==4){
	 		if(a[xx][yy+1]==0&&a[xx-1][yy]==0) continue;
		 }
		 if(i==5){
		 	if(a[xx][yy-1]==0&&a[xx-1][yy]==0) continue;
		 }
		 if(i==6){
		 	if(a[xx+1][yy]==0&&a[xx][yy-1]==0) continue;
		 }
		 if(i==8){
		 	if(a[xx+1][yy]==0&&a[xx][yy+1]==0) continue;
		 }
	 	int xz_h=a[x][y],next_h=a[xx][yy];
	 	if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]!=0){
	 		if(next_h>xz_h){
	 			high=next_h;
			 }
			 a[xx][yy]=cnt;
			 vis[xx][yy]=true;
			 dfs(xx,yy,cnt,high);
		 }
	}
	return;
} 
int main(){
	cin>>n>>m;
	memset(vis,false,sizeof(vis));
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j){
			cin>>a[i][j];
		}
	}
	int c=-1;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j){
			if(!vis[i][j]&&a[i][j]!=0){
				a[i][j]=c;
			//	cout << i << " " << j << "\n";
				ans++; 
				vis[i][j]=true;
				dfs(i,j,c,a[i][j]);
				c--;
			}
		}
	}
/*	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j){
			cout << a[i][j] << " ";
		}
		cout << "\n";
	}*/
	cout << ans;
	return 0;
}

回复

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

正在加载回复...