这是出给 pj 的题 ccccc
- #include <bits/stdc++.h>
- #define ll long long
- #define INF 2147483647
- #define y1 uihaoissa
- #define y2 oaioiuwio
- using namespace std;
- const int wx[]= {0,1,0,-1},wy[]= {1,0,-1,0};
- int T,n,m,k,maxh,ltt;
- int a[303][303],sum[303][303],cal[203];
- char tow[303][303][203];
- bool f[303][303][203];
- int cnt[303][303][203];
- short pre1[303][303][203],pre2[303][303][203],fl[303][303][203];
- bool debug;
- inline int read() {
- int x=0;
- char ch=getchar();
- while(ch<0||ch>9)ch=getchar();
- while(ch>=0&&ch<=9) {
- x=x*10+ch-0;
- ch=getchar();
- }
- return x;
- }
- inline int sqr(int x) {
- return x*x;
- }
- inline int toedge(int x,int y) {
- return min(min(x,y),min(n-x+1,m-y+1));
- }
- inline int islarge1(int x1,int y1,int y2,int z) {
- return pre1[x1][y2][z]-pre1[x1][y1-1][z];
- }
- inline int islarge2(int x1,int x2,int y1,int z) {
- return pre2[x2][y1][z]-pre2[x1-1][y1][z];
- }
- inline int getsum(int x1,int y1,int x2,int y2) {
- return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
- }
- int check(int x,int y,int z) {
- if (x>1) {
- int h;
- if (cnt[x-1][y][z]==-1)
- switch (tow[x-1][y][z]) {
- case 1:
- if (fl[x-1][y][z]!=z-1) {
- h=fl[x-1][y][z]+1;
- if (islarge1(x-h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=1,cnt[x][y][z]=-1,1;
- }
- break;
- case 2:
- h=fl[x-1][y][z];
- if (islarge2(x-h,x+h,y-h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=2,cnt[x][y][z]=-1,1;
- break;
- case 3:
- h=fl[x-1][y][z];
- if (islarge2(x-h,x+h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=3,cnt[x][y][z]=-1,1;
- break;
- case 4:
- h=fl[x-1][y][z]-1;
- if (islarge1(x+h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=4,cnt[x][y][z]=-1,1;
- break;
- }
- }
- if (y>1) {
- int h;
- if (cnt[x][y-1][z]==-1) {
- if (fl[x][y][z]==0) tow[x][y][z]=2;
- switch (tow[x][y-1][z]) {
- case 1:
- h=fl[x][y-1][z];
- if (islarge1(x-h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=1,cnt[x][y][z]=-1,1;
- break;
- case 2:
- if (fl[x][y-1][z]!=z-1) {
- h=fl[x][y-1][z]+1;
- if (islarge2(x-h,x+h,y-h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=2,cnt[x][y][z]=-1,1;
- }
- break;
- case 3:
- h=fl[x][y-1][z]-1;
- if (islarge2(x-h,x+h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=3,cnt[x][y][z]=-1,1;
- break;
- case 4:
- h=fl[x][y-1][z];
- if (islarge1(x+h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=4,cnt[x][y][z]=-1,1;
- break;
- }
- }
- }
- if (z>1) {
- if (cnt[x][y][z-1]==-1) {
- int h=fl[x][y][z-1];
- switch (tow[x][y][z-1]) {
- case 1:
- if (islarge1(x-h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=1,cnt[x][y][z]=-1,1;
- break;
- case 2:
- if (islarge2(x-h,x+h,y-h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=2,cnt[x][y][z]=-1,1;
- break;
- case 3:
- if (islarge2(x-h,x+h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=3,cnt[x][y][z]=-1,1;
- break;
- case 4:
- if (islarge1(x+h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=4,cnt[x][y][z]=-1,1;
- break;
- }
- }
- }
- for (int h=z-1; h>=0; h--) { //h 为中心到该圈的差数
- if (cnt[x][y][h+1]!=-1) break;
- if (islarge1(x-h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=1,cnt[x][y][z]=-1,1;
- if (islarge2(x-h,x+h,y-h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=2,cnt[x][y][z]=-1,1;
- if (islarge2(x-h,x+h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=3,cnt[x][y][z]=-1,1;
- if (islarge1(x+h,y-h,y+h,z-h)>0) return fl[x][y][z]=h,tow[x][y][z]=4,cnt[x][y][z]=-1,1;
- }
- int tot=cal[z]-getsum(x-z+1,y-z+1,x+z-1,y+z-1);
- return tot>k?200:(cnt[x][y][z]=tot,0);
- }
- int main() {
- for (int i=1; i<=200; i++)
- cal[i]=cal[i-1]+(2*i-1)*(2*i-1);
- T=read();
- while (T--) {
- maxh=0;
- memset(cnt,-1,sizeof(cnt));
- n=read(),m=read(),k=read();
- for (int i=1; i<=n; i++)
- for (int j=1; j<=m; j++) {
- a[i][j]=read();
- sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
- for (int k=1,to=toedge(i,j); k<=to; k++) {
- f[i][j][k]=(a[i][j]>k);
- pre1[i][j][k]=pre1[i][j-1][k]+f[i][j][k];
- pre2[i][j][k]=pre2[i-1][j][k]+f[i][j][k];
- }
- }
- for (int i=1; i<=n; i++)
- for (int j=1; j<=m; j++) {
- cnt[i][j][1]=1-a[i][j];
- if (a[i][j]<=1) maxh=max(maxh,1);
- for (int l=max(max(a[i][j],2),maxh+1),to=toedge(i,j); l<=to;) {
- int tmp=check(i,j,l);
- if (!tmp) maxh=max(maxh,l),tmp++;
- l+=tmp;
- }
- }
- printf("%d\n",maxh);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2495338.html