再一次感慨英语是多么的重要 今天打比赛写到这题一直看不懂 尤其是最关键的那个双重否定一出来我整个人就懵逼了
我还是弱弱的简单说一下题意吧
题意：
就是给你一个二维数组 每个值表示高度
给你 长 宽 和一个数d
如果一个点高度为h 只走 高度大于 h-d 的点并且达不到一个更高的点 那么这个点就是一个峰值
求峰值的数目
思路 :
贪心 从最高点出发搜索 比它小的和它连通的都标记成 原点高度 既可以标记 又可以减少访问
后面访问见注释
下面附上代码和注释
第一次用了STL的队列和优先队列 结果TLE
无奈用了模拟队列试了一下就过了
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=505;
int row,col,d;
int mat[maxn][maxn];
int vis[maxn][maxn];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
struct node
{
int x,y;
int val;
}preque[maxn*maxn],que[maxn*maxn];
bool cmp(const node& a,const node& b)
{
return a.val>b.val;
}
int bfs(int k)
{
int front=1,rear=1;
int ans=1;
vis[preque[k].x][preque[k].y]=preque[k].val;
que[front]=preque[k];
int h=preque[k].val;
bool flag=true;
while(front<=rear)
{
node temp=que[front++];
int x=temp.x,y=temp.y,val=temp.val;
for(int i=0;i<4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<=0||x>row||y<=0||y>col) continue;//不在区域内
if(h-mat[xx][yy]>=d) continue;//就如上述说的 高度必须小于h-d
if(vis[xx][yy]>h)//遇到更高的
{
flag=false;
continue ;
}
if(vis[xx][yy]==h) continue;//已访问
if(mat[xx][yy]==h) ans++;//碰到同一高度的 如果原点是 那么这个点也满足条件
vis[xx][yy]=h;//标记
que[++rear].x=xx;
que[rear].y=yy;
}
}
if(flag) return ans;
else return 0;
}
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
scanf("%d%d%d",&row,&col,&d);
int ans=0,num=0;
memset(vis,-1,sizeof vis);
for(int i=1; i<=row; i++)
for(int j=1; j<=col; j++)
{
scanf("%d",&mat[i][j]);
preque[++num].x=i;
preque[num].y=j;
preque[num].val=mat[i][j];
}
sort(preque+1,preque+1+num,cmp);
for(int i=1;i<=num;i++)
if(vis[preque[i].x][preque[i].y]==-1)
ans+=bfs(i);
printf("%d\n",ans);
}
return 0;
}