問題はこちら
No.402 最も海から遠い場所 - yukicoder
初見では解説の「無駄解法」と同じことしか思いつけなかったので、解説を見て回答
陸の部分からなる最大の正方形を見つける問題と同値になる
#define max(p,q)(p>q?p:q) #define min(p,q,r)(p<q?p<r?p:r:q<r?q:r) int a[3010][3010]; main(){ int i=1,j,t,s; gets(&t);//H,Wは要らないので読み捨て //a[i][j]は1-basedなindexとする(i-1,j-1でout of rangeにならないようにするため) while(t=~getchar()){ j++; if(t==~'#'){ a[i][j]=min(a[i-1][j],a[i-1][j-1],a[i][j-1])+1; s=max(s,a[i][j]); } else if(t==~'\n'){i++;j=0;} } printf("%d",(s+1)/2); return 0; }
取り敢えず縮める
a[3010][3010]; j,t,s; main(i){ for(gets(&t);t=~getchar();~t&1?s=fmax(s,a[i][j]=fmin(fmin(a[i-1][j],a[i-1][j-1]),a[i][j-1])+1):t&4?j=!++i:0)j++; s=!printf("%d",-~s/2); }
~t&1としている所を素直に~t==35と書けば最初のgetsが省略できる
2次元配列は面倒だからポインタを使ったほうが良さそう
改行の際に飛ぶ先を保存するのはint*とintどっちがいいか考える必要がありそう
ポインタを使うならindexは1つずらしてa[i+1][j+1]=fmin(fmin(a[i][j],a[i+1][j]),a[i][j+1])とした方が都合が良さそう
a[1<<24]; *p=a,*q; M=4e3,s; main(t){ for(;t=~getchar();q++)~t==35?s=fmax(s,q[M+1]=fmin(fmin(*q,q[1]),q[M])+1):t&4?q=p+=M:0; //*pの代わりにint型変数pを使って // for(;t=~getchar();q++)~t==35?s=fmax(s,q[M+1]=fmin(fmin(*q,q[1]),q[M])+1):t&4?q=a+(p+=M):0; //とすると、この部分が+4B、初期化が-3Bでトータル1B損 s=!printf("%d",-~s/2); }
142B