色々解法がありそう。
https://yukicoder.me/problems/no/2456
問題
N*Nのグリッドがあり、一部のマスは黒く塗られている。
K*Kのサイズの黒いスタンプを使い、同様の塗り方を再現したい。
条件を満たすKの最大値を求めよ。
解法
Kを二分探索する。
スタンプを押す位置の左上マスを総当たりしよう。
各マスを左上としてスタンプを押しても、白マスを誤って黒くしない場合、そのようなマスでスタンプを押す。
この判定は累積和を使うと各マスO(1)で可能。
その後、実際にできる模様が、入力と一致するか判定すればよい。
int H,W; string S[2020]; int D[4020][4020]; int E[4020][4020]; int ok(int v) { if(v>min(H,W)) return 0; ZERO(E); int y,x; for(y=v-1;y<H;y++) for(x=v-1;x<W;x++) { int num=D[y+1][x+1]-D[y+1-v][x+1]-D[y+1][x+1-v]+D[y+1-v][x+1-v]; if(num==v*v) E[y+1][x+1]++; } FOR(y,4010) FOR(x,4010) if(x&&y) E[y][x]+=E[y-1][x]+E[y][x-1]-E[y-1][x-1]; FOR(y,H) FOR(x,W) if(S[y][x]=='#') { if(E[y+v][x+v]-E[y][x+v]-E[y+v][x]+E[y][x]==0) return 0; } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(y,H) { cin>>S[y]; FOR(x,W) { D[y+1][x+1]=(S[y][x]=='#'); } } FOR(y,4010) FOR(x,4010) if(x&&y) D[y][x]+=D[y-1][x]+D[y][x-1]-D[y-1][x-1]; int cur=1; for(i=10;i>=0;i--) { if(ok(cur+(1<<i))) cur+=1<<i; } cout<<cur<<endl; }
まとめ
これはまぁ典型な気がするね。