首页 > 其他 > 详细

洛谷P1514 引水入城——dfs

时间:2018-06-21 20:11:22      阅读:280      评论:0      收藏:0      [点我收藏+]

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

搜索+DP;

自己想出来的方法第一次80分好高兴!

再改了改就A了,狂喜乱舞;

也就是 dfs,仔细一想第一行的每个点能覆盖到最后一行的点一定是连续的一段,否则没人能覆盖中间间断的点;

所以最上面每个点跑一遍 dfs,记下能覆盖区间的 l 和 r,再小小DP一下即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=505;
int n,m,h[maxn][maxn],f[maxn],cnt,tot,l,r,dx[5]={1,0,-1,0},dy[5]={0,1,0,-1};
bool vis[maxn][maxn],vs[maxn];
struct N{int l,r,len;}a[maxn],b[maxn];
bool cmp(N x,N y){return x.l<y.l;}
void dfs(int x,int y)
{
    vis[x][y]=1;
    if(x==n)vs[y]=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy]||h[xx][yy]>=h[x][y])continue;
        if(xx==n)l=min(l,yy),r=max(r,yy);
        dfs(xx,yy);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) scanf("%d",&h[i][j]);
    for(int i=1;i<=m;i++)
    {
        if(h[1][i-1]>h[1][i]||h[1][i+1]>h[1][i])continue;
//        l=n+1; r=0;
        l=i; r=i;//!!!
        memset(vis,0,sizeof vis);
        dfs(1,i);
        a[++cnt].l=l; a[cnt].r=r; a[cnt].len=r-l+1;
//        printf("(1,%d) l=%d r=%d\n",i,l,r);
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        if(!vs[i])ans++;
    if(ans) {printf("0\n%d",ans); return 0;}
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        while(a[i].r<=a[i-1].r&&i<=cnt)i++;
        b[++tot].l=a[i].l; b[tot].r=a[i].r;
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=tot;i++)
        for(int j=b[i].l-1;j<b[i].r;j++)
            f[b[i].r]=min(f[b[i].r],f[j]+1);
    printf("%d\n%d",1,f[m]);
    return 0;
}

 

洛谷P1514 引水入城——dfs

原文:https://www.cnblogs.com/Zinn/p/9210707.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!