読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

GCJ

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だったらよかったのに…。

広告を非表示にする