AtCoder ARC #219 : E - Equal Distribution

これ解けなかったのまずいなぁ。
https://atcoder.jp/contests/arc219/tasks/arc219_e

問題

2H*2Wのグリッドが与えられる。
このうち半分の2HWマスにはイチゴが乗っている。
この計4HWマスを、連結した２つの2HWマスの領域に分け、かつそれぞれ苺がHWマスずつあるようにせよ。

解法

4HW個のマスから、隣接マスをたどる１つのループにする。
そのうち連続する2HWマスを取ると、どこかで苺がHWマスだけ含まれるようにできる。

int T;
int H,W;
string S[2010];
vector<pair<int,int>> V;
vector<int> sum;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,2*H) {
			cin>>S[y];
		}
		V.clear();
		sum={0};
		FOR(x,2*W) {
			V.push_back({0,x});
			sum.push_back(sum.back()+(S[0][x]=='o'));
		}
		for(x=2*W-2;x>=0;x-=2) {
			for(y=1;y<2*H;y++) {
				V.push_back({y,x+1});
				sum.push_back(sum.back()+(S[y][x+1]=='o'));
			}
			for(y=2*H-1;y>=1;y--) {
				V.push_back({y,x});
				sum.push_back(sum.back()+(S[y][x]=='o'));
			}
		}
		
		FOR(y,2*H) FOR(x,2*W) S[y][x]='B';
		FOR(i,H*W*2) if(sum[i+2*H*W]-sum[i]==H*W) {
			FOR(j,2*H*W) S[V[i+j].first][V[i+j].second]='A';
			break;
		}
		FOR(y,2*H) cout<<S[y]<<endl;
		
		
	}
}

まとめ

うーん、近いこと考えたのにゴールまでたどり着けず残念。