p2919
查看原帖
p2919
1329138
luogu_hezhenmin1楼主2024/9/11 21:47
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,sum,f;
}a[490008];
int n,m,cnt,ans,s[702][702];
int id[702][702];
bool vis[702][702];
int dxy[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
bool cmp(node a,node b){
	return a.sum>b.sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=m;j++){
	   	    cin>>s[i][j];
	   	    a[++cnt]={i,j,s[i][j],0};
	   }
	sort(a+1,a+cnt+1,cmp);
	id[1][1]=1;
	for(int i=1;i<=cnt;i++)
		id[a[i].x][a[i].y]=i;
	queue<pair<int,int> > q;
	for(int i=1;i<=cnt;i++){
		if(a[i].f==0 and a[i].sum>0){
			ans++;
			q.push({a[i].x,a[i].y});
			a[i].f=1;
			while(!q.empty()){
				pair<int,int> k=q.front();q.pop();
				int x=k.first,y=k.second;
				for(int j=0;j<8;j++){
					int nx=x+dxy[j][0],ny=y+dxy[j][1];
					if(nx<1 or ny<1 or nx>n or ny>m) continue;
					if(s[nx][ny]==0) continue;
					if(s[nx][ny]>s[x][y]) continue;
					if(vis[nx][ny]==1) continue;
					vis[nx][ny]=1;
					a[id[nx][ny]].f=1;
					q.push({nx,ny});
				}
			}
		}
	}
	cout<<ans;
	return 0;
} 
2024/9/11 21:47
加载中...