自动搬运

查看原文

来自洛谷，原作者为

	素质玩家孙1超 天道酬勤！

搬运于2025-08-24 21:43:26，当前版本为作者最后更新于2019-08-12 12:06:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题原来我没看懂题目意思，被坑了好久。

其实题目意思不是非常明确（疯狂甩锅）

题意：

在矩阵中，如果一个元素的高度大于等于其他邻接的 八个 元素（其中有可能有

边界），那么他可以作为一个山丘的顶，并那八个元素可以向外扩散，形成严格

不上升的区块。

要点：

注意，由于一个山丘里面可能包含另一个山丘，所以如果不处理的话，答案会

偏大。正确的做法是从最大的开始搜索，可以有效防止重复。

代码：我对我的代码还是有点信心的

#include<bits/stdc++.h>
using namespace std;
int R()//快读 
{
	char c;int sign=1,res=0;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;
	res+=c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;	
}
const int dx[8]={1,-1,0,0,1,1,-1,-1};
const int dy[8]={0,0,1,-1,-1,1,1,-1};
struct point//用来排序的结构体 
{
	int x,y,h;	
}a[1010*1010];
bool cmp(point x,point y)
{
	return x.h>y.h; 
} 
int n,m,ans;
int q[1010][1010];//矩阵 
bool flag[1010][1010];//记录 
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(!flag[x+dx[i]][y+dy[i]]&&q[x+dx[i]][y+dy[i]]<=q[x][y])
			dfs(x+dx[i],y+dy[i]);
}
int main()
{
	n=R();m=R();
	int o=0;
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++)
		{
			q[i][j]=R();
			a[++o].h=q[i][j];
			a[o].x=i;a[o].y=j;
		}
//以上是读入 
	sort(a+1,a+1+o,cmp);
	for(int i=1;i<=o;i++)//从最大的开始搜 
	{
		int x=a[i].x,y=a[i].y;
		if(!flag[x][y])//如果没去过 
		{
			bool f=1;
			for(int p=0;p<8;p++)//判断是否可以作为山顶 
				if(q[x][y]<q[x+dx[p]][y+dy[p]])
					f=0;
			if(f)
				dfs(x,y),ans++;//搜索出整个山丘 
		}
	}
	cout<<ans;
}