这题。。。
以前打的，很暴力的bfs：
#include<cstdio>
#include<cstring>
using namespace std;
int a[502][502],ll[502],rr[502],data[300001][2];
bool bz[502][502];
int temp,n,m;
const int way[5][2]={-1,0,1,0,0,-1,0,1};
void bfs(int x,int y)
{
int l=0,r=1,i,xx,yy;
memset(data,0,sizeof(data));
data[1][0]=x;
data[1][1]=y;
while (l<r)
{
l++;
for (i=0;i<4;i++)
{
xx=data[l][0]+way[i][0];
yy=data[l][1]+way[i][1];
if (xx>0&&yy>0&&xx<=n&&yy<=m&&a[xx][yy]<a[data[l][0]][data[l][1]]&&bz[xx][yy]==false)
{
bz[xx][yy]=true;
r++;
data[r][0]=xx;data[r][1]=yy;
}
}
}
}
void dg(int x,int y)
{
int l=0,r=1,i,xx,yy;
memset(data,0,sizeof(data));
memset(bz,0,sizeof(bz));
data[1][0]=x;
data[1][1]=y;
while (l<r)
{
l++;
for (i=0;i<4;i++)
{
xx=data[l][0]+way[i][0];
yy=data[l][1]+way[i][1];
if (xx>0&&yy>0&&xx<=n&&yy<=m&&a[xx][yy]<a[data[l][0]][data[l][1]]&&bz[xx][yy]==false)
{
bz[xx][yy]=true;
r++;
data[r][0]=xx;data[r][1]=yy;
}
}
}
for (i=1;i<=m;i++)
{
if (bz[n][i]==false) continue;
if (ll[temp]==0) ll[temp]=i;
rr[temp]=i;
}
}
int main()
{
int i,j,k=0,ans=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for (i=1;i<=m;i++) bfs(1,i);
for (i=1;i<=m;i++)
{
if (bz[n][i]==false) k++;
}
if (n==1)
{
printf("1
%d
",k);
}
else if (k>0)
{
printf("0
%d
",k);
}
else
{
for (i=1;i<=m;i++)
{
temp=i;
dg(1,i);
}
i=1;
k=0;
while (i<=m)
{
for (j=1;j<=m;j++)
{
if (ll[j]<=i&&rr[j]>k) k=rr[j];
}
i=k+1;
ans++;
}
printf("1
%d
",ans);
}
}
这题其实可以贪心的。
因为不难发现，第一层要选的有一个条件：
a[1][i]>a[1][i-1] && a[1][i]>a[1][i+1]
因为这样才算优嘛。
然后就是一个性质了：
它所流到的第n层一定是一段连续的区间。
如果不是的话，那就输出0吧~
思考一下，为什么呢？
因为如果不是一段连续的区间，那么它中间断掉的地方则永远都留不到！
好了，就说到这里了，自己在想想吧。
上标：
#include<cstdio>
#include<cstring>
#define min(x,y) x=x<y ? x:y
#define max(x,y) x=x>y ? x:y
using namespace std;
int a[501][501],l[501],r[501],n,m,ans,fr;
bool bz[501][501],c[501];
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
void dg(int x,int y)
{
bz[x][y]=1;
if (x==n) {c[y]=1,min(l[fr],y),max(r[fr],y);}
if (y>1 && a[x][y]>a[x][y-1] && !bz[x][y-1]) dg(x,y-1);
if (y<m && a[x][y]>a[x][y+1] && !bz[x][y+1]) dg(x,y+1);
if (x>1 && a[x][y]>a[x-1][y] && !bz[x-1][y]) dg(x-1,y);
if (x<n && a[x][y]>a[x+1][y] && !bz[x+1][y]) dg(x+1,y);
}
int main()
{
freopen("flow.in","r",stdin);
// freopen("flow.out","w",stdout);
n=read(),m=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]=read();
for (int i=1;i<=m;i++) l[i]=m+1;
for (int i=1;i<=m;i++)
{
memset(bz,0,sizeof(bz));
if (a[1][i]>=a[1][i-1] && a[1][i]>=a[1][i+1]) fr=i,dg(1,i);
}
for (int i=1;i<=m;i++) ans+=(!c[i]);
if (ans) return 0&printf("0
%d
",ans);
for (int i=1,x=0;i<=m;i=x+1,ans++)
for (int j=1;j<=m;j++)
if (l[j]<=i && r[j]>=x) x=r[j];
printf("1
%d
",ans);
return 0;
}