Codeforces #706 Div1 : C. Garden of the Sun

コードは短い。
https://codeforces.com/contest/1495/problem/C

問題

白黒で塗られたグリッドがある。
初期状態で黒マス同士は隣接しない。

ここでいくつか白マスを黒マスにし、以下を満たすようにせよ。

• 黒マス同士はすべて連結
• 黒マス間の移動経路は常に一意に定まる。

解法

色々解法がありそう。
自分は以下のようにした。

• 3列ごとにすべて黒く塗る
• 基本的に最上位行をすべて黒く塗る。
  • ただし、3列ごと以外の列で2行目に黒マスがある場合、最上位行でなく2行目で隣接する3列間をつなぐ。

int A;
int H,W;
string S[500],T[500];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A;
	while(A--) {
		cin>>H>>W;
		FOR(y,H) {
			cin>>S[y];
			T[y]=string(W,'.');
		}
		FOR(x,W) T[0][x]='X';
		int s=0;
		if(W%3==0) s=1;
		else s=0;
		for(x=s;x<W;x+=3) FOR(y,H) T[y][x]='X';
		FOR(y,H) FOR(x,W) if(S[y][x]=='X') T[y][x]='X';
		
		if(H>=2) {
			FOR(x,W) if(x%3!=s&&T[1][x]=='X') {
				if(x) T[1][x-1]='X';
				if(x<W) T[1][x+1]='X';
			}
			FOR(x,W) if(x%3!=s&&T[1][x]=='X') T[0][x]='.';
			
		}
		
		FOR(y,H) cout<<T[y]<<endl;
		
	}
}

まとめ

結果だけ見るとすごい簡単だけど、本番かなり苦戦してるな。