dfs
查看原帖
dfs
751817
l_m_pigeon楼主2024/9/11 21:54
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt=0,ans=0;
int h[801][801];
int flag[701][701];
int dx[8]={1,-1,0,0,1,1,-1,-1};
int dy[8]={0,0,1,-1,-1,1,1,-1};
struct high{
	int x,y,h;
}a[801*801];
bool cmp(high i,high j){
	return i.h>j.h;				
}
void dfs(int x,int y){
	if(x>n||y>m||!x||!y){
		return;
	}
	flag[x][y]=1;
	for(int i=0;i<8;i++){
		if(h[x][y]>=h[x+dx[i]][y+dy[i]]&&!flag[x+dx[i]][y+dy[i]]){
			dfs(x+dx[i],y+dy[i]);
		}
	}
}
int main(){
	cin>>n>>m;
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>h[i][j];
			a[++cnt]={i,j,h[i][j]};
		}
	}
	sort(a+1,a+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){
		int x=a[i].x,y=a[i].y;
		if(!flag[x][y]){
			bool f=1;
			for(int j=0;j<8;j++){
				if(h[x][y]<h[x+dx[j]][y+dy[j]]){
					f=0;
				}
			}
			if(f){
				ans++;
				dfs(x,y);
				
			}
		}
	}
	cout<<ans;
} 
2024/9/11 21:54
加载中...