60分 2 3 8 10点过不去求助!

#include #include #include #include #define MAXN 510 using namespace std; int n,m; int h[MAXN][MAXN];//高度 int fi[MAXN],numi=0; int la[MAXN],numa=0; //离散化 //bool fit[MAXN][MAXN],lat[MAXN][MAXN]; //标记

bool vis[MAXN][MAXN];//访问标记 int fx[]={-1,0,1, 0}; int fy[]={ 0,1,0,-1}; int ss=0; inline bool dfs1(int x,int y) { if(x == n) ss++; if(ss == m) return true; for(int i=0;i<4;i++) { int nx=x+fx[i],ny=y+fy[i]; if(nx<1 || nx>n || ny<1 || ny>m) continue; if(h[nx][ny]>=h[x][y]) continue; if(vis[nx][ny]) continue; vis[nx][ny]=1; if( dfs1(nx,ny) ) return true; } return false; } //填充而非回溯

struct Seg { int l,r; bool operator < (const Seg& rhs) const { if(this->l == rhs.l) return this->r > rhs.r; return this->l < rhs.l; } }; Seg s[MAXN]; int nums=0;

int ll=m+1,rr=0; inline void dfs2(int x,int y) { if(x == n) { ll=min(ll,y); rr=max(rr,y); } for(int i=0;i<4;i++) { int nx=x+fx[i],ny=y+fy[i]; if(nx<1 || nx>n || ny<1 || ny>m) continue; if(h[nx][ny]>=h[x][y]) continue; if(vis[nx][ny]) continue; vis[nx][ny]=1; dfs2(nx,ny); vis[nx][ny]=0; } } int ans=0; 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] >= h[1][i+1]) fi[++numi]=i; if(h[n][i-1] <= h[n][i] && h[1][i] >= h[1][i+1]) la[++numa]=i; }//记录波峰

CPP

for(int i=1;i<=numi;i++) {
    if(vis[1][fi[i]]) continue;
    vis[1][fi[i]]=true;
    dfs1(1,fi[i]);
}//先看看能不能到 

if(ss < m) {
    printf("0\n%d",m-ss); return 0;
}//到不了就输出 

for(int i=1;i<=numi;i++) {
    memset(vis,0,sizeof(vis));
    ll=m+1; rr=0;
    vis[1][fi[i]]=1;
    dfs2(1,fi[i]);
    vis[1][fi[i]]=0;
    if(ll==m+1 && rr==0) continue;
    s[++nums].l=ll; s[nums].r=rr;
}
sort(s+1,s+1+nums);
int tail=s[1].r;//尾部的 
ans++;
for(int i=2;i<=nums;i++) {
    if(s[i].l>tail+1 || s[i].r<=tail) continue;
    ans++; tail=s[i].r;
}
printf("1\n%d",ans);
return 0;

}

60分 2 3 8 10点过不去求助!

讨论操作

回复

相关推荐

60分 2 3 8 10点过不去求助!