bzoj1619

题解：

简单灌水

从最高的开始

代码：

#include<bits/stdc++.h>

const int inf=0x7fffffff,N=;

typedef long long ll;

using namespace std;

int n,m,cnt,ans,xx[]={,,,,,-,-,-},yy[]={,-,,,-,,,-},mp[N][N],mark[N][N];

struct data{int x,y,t;}a[];

bool operator<(data a,data b){return a.t>b.t;}

void dfs(int x,int y)

{

    mark[x][y]=;

    for (int i=;i<;i++)

     {

        int nowx=x+xx[i],nowy=y+yy[i];

        if (nowx<||nowy<||nowx>n||nowy>m)continue;

        if (mp[nowx][nowy]<=mp[x][y]&&!mark[nowx][nowy])dfs(nowx,nowy);

     }

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)

     for (int j=;j<=m;j++)

      {

        cnt++;

        scanf("%d",&mp[i][j]);

        a[cnt].x=i;a[cnt].y=j;a[cnt].t=mp[i][j];

      }

    sort(a+,a+cnt+);

    for (int i=;i<=cnt;i++)

     if (!mark[a[i].x][a[i].y]){dfs(a[i].x,a[i].y);ans++;}

    printf("%d",ans);

    return ;

}