問題文の図が妙に明るくて見づらい。
https://codeforces.com/contest/1280/problem/B
問題
各セルにA,Pのいずれかが書かれたグリッドが与えられる。
幅または高さ1の区間を選択し、上下左右選択した方向にそれを端までペーストする、という作業を繰り返して全体をAだけにしたい。
最小何回ペーストが必要か。
解法
1つのAから始める場合、上下左右端じゃないところから始めるごとに1手余分にかかる。
元々1列または1行Aで埋まっている場合は、左右または上下だけペーストする必要があるかそれぞれ求めればよい。
int T; int H,W; string S[61]; int A[70][70]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>H>>W; int mi=1010; int numP=0; FOR(y,H) { cin>>S[y]; FOR(x,W) numP+=S[y][x]=='P'; } if(numP==0) mi=0; FOR(y,H) FOR(x,W) if(S[y][x]=='A') { int need=0; if(y) need++; if(x) need++; if(y<H-1) need++; if(x<W-1) need++; mi=min(mi,need); } FOR(y,H) { int num=0; FOR(x,W) if(S[y][x]=='P') num++; if(num==0) mi=min(mi,(y>0)+(y<H-1)); } FOR(x,W) { int num=0; FOR(y,H) if(S[y][x]=='P') num++; if(num==0) mi=min(mi,(x>0)+(x<W-1)); } if(mi>4) { cout<<"MORTAL"<<endl; } else { cout<<mi<<endl; } } }
まとめ
これも750ptでいい気がする。
この回前半が妙に簡単だったっぽいな。