Google Code Jam 2010 Round2 A.Elegant Diamond

Google Code Jam 実装問題

本番で解けなかったやつorz
力もないのに見切り発車で実装するのがだめなのかもなあ。

問題概要

サイズkのダイアモンドが与えられる。これに数字をいくつか書き加えて「エレガントな」ダイアモンドにしたい。書き加える数の数の最小値を求めよ。


サイズkのダイアモンドとは、
1行目からk行目にそれぞれ1個、2個、...、k個の数字が並び、
k+1行目から2*k-1行目にそれぞれk-1個、k-2個、...、1個の数字が並んだものをいう。


ダイアモンドがエレガントであるとは、ダイアモンドが行に関して線対称であり、
列に関しても線対称であることをいう。


例）

  1
 2 2
3 4 3
 2 2
  1

k≦51である。

解法

すでにある対称軸を総当りで探す。
そのような対称軸のうち、元々の中心に最も近いところを大きなダイヤの中心とすればよい。


各数字は0-9であるので文字列のまま読み込む。
元々の中心と新たな中心のマンハッタン距離をdとすれば、
新たなダイヤのサイズはd+kである。（これらで大分実装が簡潔になるっぽい）

ソースコード

int k;
vs dia;
bool sayuu[200],jouge[200];

bool sayuuOK(int x)
{
	rep(i,2*k-1)rep(j,2*k-1)
	if(0<=2*x-j&&2*x-j<2*k-1)
	if(dia[i][j]!=' '&&dia[i][2*x-j]!=' ')
	if(dia[i][j]!=dia[i][2*x-j])return 0;
	
	return 1;
}
bool jougeOK(int y)
{
	rep(i,2*k-1)rep(j,2*k-1)
	if(0<=2*y-i&&2*y-i<2*k-1)
	if(dia[i][j]!=' '&&dia[2*y-i][j]!=' ')
	if(dia[i][j]!=dia[2*y-i][j])return 0;
	
	return 1;
}

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		cin>>k; cin.ignore();
		dia=vs(2*k-1);
		
		rep(i,2*k-1)
		{
			getline(cin,dia[i]);
			while(dia[i].size()<2*k-1)dia[i].pb(' ');
		}
		
		rep(i,2*k-1)sayuu[i]=sayuuOK(i);
		rep(i,2*k-1)jouge[i]=jougeOK(i);
		
		int ans=inf;
		rep(i,2*k-1)rep(j,2*k-1)if(sayuu[i]&&jouge[j])
		ans=min(ans,abs(k-1-i)+abs(k-1-j));
		
		ans=(ans+k)*(ans+k)-k*k;
		
		cout<<"Case #"<<cs+1<<": "<<ans<<endl;
	}
	
	return 0;
}