左上角和右下角不四連通等價于左下角和右上角八連通

枚舉正方形的左上角，先二分出最大的邊長，使得里面不含障礙物

然后再二分出最小的邊長，使得兩部分連通，用前綴和判斷

?

這題WA了好久…一直對拍都沒問題…于是去看原題，發現有SPJ…

然后改了個枚舉姿勢就過了…

?

#include<cstdio> #define N 1510 int n,m,i,j,dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1},x[N*N],y[N*N],h,t,sum[3][N][N],ans,ansx,ansy,l,r,mid; char s[N]; bool a[N][N],v[N][N]; inline int min(int&a,int b){if(a>b)a=b;} inline int max(int&a,int b){if(a<b)a=b;} inline int ask(int p,int x,int y,int k){int x1=x-1,y1=y-1,x2=x+k-1,y2=y+k-1;max(x1,0),max(y1,0),min(x2,n),min(y2,m);return sum[p][x2][y2]-sum[p][x1][y2]-sum[p][x2][y1]+sum[p][x1][y1]; } inline void add(int nx,int ny){if(nx<1||nx>n||ny<1||ny>m||!a[nx][ny]||v[nx][ny])return;v[nx][ny]=1,x[++t]=nx,y[t]=ny; } inline void bfs(int nx,int ny){for(h=1,t=0,add(nx,ny);h<=t;h++)for(j=0;j<8;j++)add(x[h]+dx[j],y[h]+dy[j]);} int main(){scanf("%d%d",&m,&n);gets(s);for(i=1;i<=n;i++)for(gets(s+1),j=1;j<=m;j++)a[i][j]=s[j]=='#';a[1][1]=a[n][m]=1;for(i=1;i<=n;i++)for(j=1;j<=m;j++)sum[0][i][j]=sum[0][i-1][j]+sum[0][i][j-1]-sum[0][i-1][j-1]+a[i][j];a[1][1]=a[n][m]=0;for(i=1;i<=n;i++)bfs(i,1);for(i=1;i<=m;i++)bfs(n,i);for(i=1;i<=n;i++)for(j=1;j<=m;j++)sum[1][i][j]=sum[1][i-1][j]+sum[1][i][j-1]-sum[1][i-1][j-1]+v[i][j],v[i][j]=0;for(i=1;i<=n;i++)bfs(i,m);for(i=1;i<=m;i++)bfs(1,i);for(i=1;i<=n;i++)for(j=1;j<=m;j++)sum[2][i][j]=sum[2][i-1][j]+sum[2][i][j-1]-sum[2][i-1][j-1]+v[i][j];ans=N;for(i=1;i<=n;i++)for(j=1;j<=m;j++){l=1,r=n-i+1,min(r,m-j+1),min(r,ans-1),t=0;while(l<=r){mid=(l+r)>>1;if(!ask(0,i,j,mid))l=(t=mid)+1;else r=mid-1;}l=1,r=t;while(l<=r){mid=(l+r)>>1;if((ask(1,i-1,j-1,mid+2)||j==1||i+mid-1==n)&&(ask(2,i-1,j-1,mid+2)||i==1||j+mid-1==m))ans=mid,ansx=i,ansy=j,r=mid-1;else l=mid+1;}}if(ans==N)puts("Impossible");else printf("%d %d %d",ans,ansy,ansx);return 0; }

　　

?

轉載于:https://www.cnblogs.com/clrs97/p/4403182.html

總結

以上是生活随笔為你收集整理的BZOJ3808 : Neerc2012 Labyrinth of the Minotaur的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。