这道题 解决第一问 用灌水法 枚举第一行的每一个点 查找是否最后一行的每一个点是否都能灌到水
第二问 用反灌水发 枚举最后一行的每一个点 解决第一行每一个点所能覆盖的左右端点 可以证明每个点所能覆盖的点是连续的一条线段 （反证法）
tips 数组是可以直接被调用 在函数中修改可以直接修改原数组
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int M=505; 6 int n,m,qx[M*M],qy[M*M],xi[5]={0,0,1,0,-1},yi[5]={0,1,0,-1,0}; 7 int map[M][M],l[M][M],a[M][M],r[M][M]; 8 struct node{int l,r;}e[M]; 9 int cmp(node a,node b){return a.l==b.l?a.r>b.r:a.l<b.l;} 10 int read(){ 11 int ans=0,f=1; int c=getchar(); 12 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 13 while(c>='0'&&c<='9') {ans=ans*10+(c-'0'); c=getchar();} 14 return ans*f; 15 } 16 void bfs(int b[M][M],int nx,int ny,int v,int f){ 17 int head=0,tail=1; qx[0]=nx; qy[0]=ny; b[nx][ny]=v; 18 while(head!=tail){ 19 int x=qx[head],y=qy[head]; head++; 20 for(int i=1;i<=4;i++){ 21 int sx=x+xi[i],sy=y+yi[i]; 22 if(sx<1||sy<1||sx>n||sy>m||b[sx][sy]) continue; 23 if(!f&&a[sx][sy]>=a[x][y]) continue; 24 if(f&&a[sx][sy]<=a[x][y]) continue; 25 b[sx][sy]=v; qx[tail]=sx; qy[tail]=sy; tail++; 26 } 27 } 28 } 29 int main() 30 { 31 n=read(); m=read(); 32 for(int i=1;i<=n;i++) 33 for(int j=1;j<=m;j++) 34 a[i][j]=read(); 35 for(int i=1;i<=m;i++) if(!map[1][i]) bfs(map,1,i,1,0); 36 int tot=0; for(int i=1;i<=m;i++) if(!map[n][i]) tot++; 37 if(tot){ 38 printf("0 %d ",tot); 39 return 0; 40 } 41 for(int i=1;i<=m;i++) if(!l[n][i]) bfs(l,n,i,i,1); 42 for(int i=m;i>=1;i--) if(!r[n][i]) bfs(r,n,i,i,1); 43 for(int i=1;i<=m;i++){ 44 if(!l[1][i]) l[1][i]=r[1][i]; 45 if(!r[1][i]) r[1][i]=l[1][i]; 46 e[i].l=l[1][i]; e[i].r=r[1][i]; 47 } 48 sort(e+1,e+1+m,cmp); 49 int to=0,now=0; 50 for(int i=1;i<=m;i++){ 51 if(now+1>=e[i].l) to=max(to,e[i].r); 52 else now=to,to=max(e[i].r,to),tot++; 53 } 54 if(now!=m) tot++; 55 printf("1 %d ",tot); 56 return 0; 57 }
