Codeforces #607 Div1 B. Beingawesomeism

問題文の図が妙に明るくて見づらい。
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でいい気がする。
この回前半が妙に簡単だったっぽいな。