BFS

POJ 3503 Summits

再一次感慨英语是多么的重要 今天打比赛写到这题一直看不懂 尤其是最关键的那个双重否定一出来我整个人就懵逼了
我还是弱弱的简单说一下题意吧

题意:
就是给你一个二维数组 每个值表示高度
给你 长 宽 和一个数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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注