Google Code Jam 2017 Round 1A : A. Alphabet Cake

B-largeが自信ないし、C-largeはダメダメそうだったのになぜか通ってびっくり。
https://code.google.com/codejam/contest/5304486/dashboard#s=p0

問題

二次元グリッドがある。
いくつかのマスには異なるアルファベットが埋められている。

各マスを以下の条件を満たすように、登場しているアルファベットで埋めよ。

• 同じアルファベットが埋まるマス群は矩形を成す。
• 最初からアルファベットが埋められているマスは変えてはならない。

解法

まずは行内を埋めた後、行単位で埋めていく。

前半、各行で1文字でもアルファベットが存在するなら、それらを他のアルファベットにぶつかるまで左右に伸ばして(コピーして)いこう。
こうすると各行はすべて埋まっているか空かのいずれかである。

あとは、空の行については上下の行を見て、埋まっている行があればそれを上下の空行にコピーしよう。

int H,W;
string S[30];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W-1) if(S[y][x]!='?' && S[y][x+1]=='?') S[y][x+1]=S[y][x];
		for(x=W-1;x>=1;x--) if(S[y][x]!='?' && S[y][x-1]=='?') S[y][x-1]=S[y][x];
	}
	FOR(y,H-1) if(S[y][0]!='?' && S[y+1][0]=='?') S[y+1]=S[y];
	for(y=H-1;y>=1;y--) if(S[y][0]!='?' && S[y-1][0]=='?') S[y-1]=S[y];
	
	_P("Case #%d:\n",_loop);
	FOR(y,H) _P("%s\n",S[y].c_str());
}

まとめ

今回がRound2だったらよかったのに…。