洛谷P1514 引水入城

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 inline int read(void){
 6     int x=0,f=1;char ch=getchar();
 7     while(ch<‘0‘||ch>‘9‘){
 8         if(ch==‘-‘) f=-1;
 9         ch=getchar();
10     }
11     while(ch>=‘0‘&&ch<=‘9‘){
12         x=(x<<1)+(x<<3)+ch-‘0‘;
13         ch=getchar();
14     }
15     return x*f;
16 }
17 
18 bool flag[505][505],can[505];
19 int n,m,h[505][505],ans,f[505],l[505],r[505];
20 
21 void dfs(int x,int y,int k){
22     if(x<1||x>n||y<1||y>m) return;
23     flag[x][y]=1;
24     if(x==n){
25         can[y]=1;
26         l[k]=min(l[k],y);
27         r[k]=max(r[k],y);
28     }
29     if(!flag[x+1][y]&&h[x+1][y]<h[x][y]) dfs(x+1,y,k);
30     if(!flag[x][y+1]&&h[x][y+1]<h[x][y]) dfs(x,y+1,k);
31     if(!flag[x-1][y]&&h[x-1][y]<h[x][y]) dfs(x-1,y,k);
32     if(!flag[x][y-1]&&h[x][y-1]<h[x][y]) dfs(x,y-1,k);
33 }
34 
35 void dp(){
36     memset(f,0x3f,sizeof(f));
37     f[0]=0;
38     for(register int i=1;i<=m;i++)
39         for(register int j=1;j<=m;j++)
40             if(i>=l[j]&&i<=r[j])
41                 f[i]=min(f[i],f[l[j]-1]+1);
42     printf("1\n%d",f[m]);
43 }
44 
45 int main(){
46     memset(l,0x3f,sizeof(l)); 
47     n=read();m=read();
48     for(register int i=1;i<=n;i++)
49         for(register int j=1;j<=m;j++)
50             h[i][j]=read();
51     for(register int i=1;i<=m;i++)
52         if(h[1][i]>=h[1][i-1]&&h[1][i]>=h[1][i+1]){
53             memset(flag,0,sizeof(flag));
54             dfs(1,i,i);
55         }
56     for(register int i=1;i<=m;i++)
57         if(!can[i])
58             ans++;
59     if(ans) printf("0\n%d",ans);
60     else dp();
61     return 0;
62 }