洛谷 1514 (NOIp2010) 引水入城

题目：https://www.luogu.org/problemnew/show/P1514

如果有解，一个第一行的格子能覆盖第n行的一定是一个连续的区间。

　　因为如果不连续，则有围住了一些第n行的格子却流不过去的情况。这样被围住的格子肯定谁都流不到它。

！！必须加第54行的判断！不然会无限TLE。dfs似乎是爆栈。那bfs为什么也不行？

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=;

int n,m,a[N][N],ct;

int fx[]={-,,,},fy[]={,-,,};

bool fg[N],vis[N][N];

struct Node{

    int l,r;

}b[N],q[N];

bool check(int x,int y,int i)

{

    int tx=x+fx[i],ty=y+fy[i];

    if(tx>=&&tx<=n&&ty>=&&ty<=m&&a[tx][ty]<a[x][y]&&!vis[tx][ty])return true;

    return false;

}

void dfs(int x,int y,int rt)

{

    vis[x][y]=;

    if(x==n){

        fg[y]=;b[rt].l=min(b[rt].l,y);

        b[rt].r=max(b[rt].r,y);

    }

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

        if(check(x,y,i))

            dfs(x+fx[i],y+fy[i],rt);

}

//void bfs(int rt)

//{

//    queue<pair<int,int> > qu;

//    qu.push(make_pair(1,rt));vis[1][rt]=1;

//    while(qu.size())

//    {

//        int x=qu.front().first,y=qu.front().second;

//        qu.pop();

//        if(x==n){fg[y]=1;b[rt].l=min(b[rt].l,y);b[rt].r=max(b[rt].r,y);}

//        for(int i=0;i<4;i++) if(check(x,y,i))

//        {

//            vis[x+fx[i]][y+fy[i]]=1;

//            qu.push(make_pair(x+fx[i],y+fy[i]));

//        }

//    }

//}

bool cmp(Node u,Node v){return u.l==v.l?u.r>v.r:u.l<v.l;}

int main()

{

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

    for(int i=;i<=n;i++)for(int j=;j<=m;j++)scanf("%d",&a[i][j]);

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

    {

        if(a[][i-]>a[][i]||a[][i+]>a[][i])continue;////////

        memset(vis,,sizeof vis);vis[][i]=;

        b[i].l=m+;dfs(,i,i);

    }

    int cnt=;

    for(int i=;i<=m;i++)if(!fg[i])cnt++;

    if(cnt){

        printf("0\n%d",cnt);return ;

    }

    sort(b+,b+m+,cmp);

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

    {

        q[++ct]=b[i];

        while(b[i].l==b[i+].l)i++;

    }

    q[ct+].l=m+;

    int now=,cr=,k=;

    while(now<m)

    {

        for(;q[cr].l<=now+;cr++)k=max(k,q[cr].r);

        now=k;cnt++;

    }

    printf("1\n%d",cnt);

    return ;

}