1102: [POI2007]山峰和山谷Grz

【题目描述】

【解题报告】

这题很水，按照高度排序，BFS一下就可以了。

代码如下

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define Par pair
          
           using namespace std;const int f[8][2]={ { 1,-1},{ 1,0},{ 1,1},{ 0,-1},{ 0,1},{-1,1},{-1,0},{-1,-1}};int n,mp[1005][1005],Ans1,Ans2;bool vis[1005][1005];queue
           
             que;struct xcw{ int x,y,w; bool operator<(const xcw b)const{ return w
            
             n||y<1||y>n) return 0; return !vis[x][y];}void BFS_UP(int x,int y){ que.push(make_pair(x,y));vis[x][y]=1; while(!que.empty()){ x=que.front().first,y=que.front().second;que.pop(); for(int i=0;i<8;i++) if(check(x+f[i][0],y+f[i][1])&&mp[x][y]<=mp[x+f[i][0]][y+f[i][1]]){ vis[x+f[i][0]][y+f[i][1]]=1; que.push(make_pair(x+f[i][0],y+f[i][1])); } }}void BFS_DOWN(int x,int y){ que.push(make_pair(x,y));vis[x][y]=1; while(!que.empty()){ x=que.front().first,y=que.front().second;que.pop(); for(int i=0;i<8;i++) if(check(x+f[i][0],y+f[i][1])&&mp[x][y]>=mp[x+f[i][0]][y+f[i][1]]){ vis[x+f[i][0]][y+f[i][1]]=1; que.push(make_pair(x+f[i][0],y+f[i][1])); } }}int main(){ #ifndef ONLINE_JUDGE freopen("prob.in","r",stdin); freopen("prob.out","w",stdout); #endif n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=read(),a[(i-1)*n+j]=(xcw){i,j,mp[i][j]}; sort(a+1,a+1+n*n); for(int i=1;i<=n*n;i++) if(!vis[a[i].x][a[i].y]) BFS_UP(a[i].x,a[i].y),Ans1++; memset(vis,0,sizeof(vis)); for(int i=n*n;i;i--) if(!vis[a[i].x][a[i].y]) BFS_DOWN(a[i].x,a[i].y),Ans2++; printf("%d %d\n",Ans2,Ans1); return 0;}