bzoj [POI2007]POW-The Flood

题解忘了......

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <queue>
#define N 1005
using namespace std;
 
int vis[N][N],viss[N][N];
int mapp[N][N];
int dx[6]={-1,1,0,0},dy[6]={0,0,-1,1};
struct node
{
    int x;int y;int he;
}poi[N*N];
int cmp(node a,node b)
{
    return a.he<b.he;
}
int ctt;
int qx[N*N],qy[N*N],bo[N][N];
int pre=0;
int bfs(int x,int y)
{
    pre++;
    bo[x][y]=pre;
    qx[1]=x,qy[1]=y;
    int h=1,t=1,nx,ny,nh=mapp[x][y];
    while(h<=t)
    {
        nx=qx[h];
        ny=qy[h++];
        for(int i = 0;i < 4;i++)
        {
            int xx=nx+dx[i],yy=ny+dy[i];
            if(vis[xx][yy]&&bo[xx][yy]!=pre&&mapp[xx][yy]<=nh)
            {
                bo[xx][yy]=pre;
                qx[++t]=xx;qy[t]=yy;
                if(viss[xx][yy]) return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            vis[i][j]=1;
            int x;
            scanf("%d",&x);
            if(x>0)
            {
                mapp[i][j]=x;
                poi[++cnt].x=i;
                poi[cnt].y=j;
                poi[cnt].he=x;
                bo[i][j]=1;
            }else mapp[i][j]=-x;
        }
    }
    sort(poi+1,poi+1+cnt,cmp);
    int ans=0;
    for(int i = 1;i <= cnt;i++)
    {
        if(!bfs(poi[i].x,poi[i].y)) ans++;
        viss[poi[i].x][poi[i].y]=1;
    }
    printf("%d\n",ans);
    return 0 ;
}