TopCoder, SRM 638, Division 1, Level 1 : ShadowSculpture

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081

問題概要

　複数の単位立方体からなる立体をつくる。立体を構成する単位立方体は、 の立方体を構成する単位立方体の部分集合である。
　作られる立体は、2 つの条件を満たさなければならない。
　まず、作られる立体を XY, YZ, ZX 平面に射影した結果は、与えられるサイズ の文字列配列 によって規定される。各文字列配列中に含まれる文字列は 'Y', 'N' からなり、'Y' は立体を射影したときに影になる部分に対応し、'N' はそれ以外の場合に対応する。形式的に述べると、座標 に単位立方体が配置されている場合、かつそのときに限り である。
　また、つくられる立体は 6-connected でなければならない。すなわち、立体を構成する単位立方体のうち 2 つが面を接しているとき、その 2 つは連結であるとした場合に、立体全体が一つの連結成分になっていなければならない。
　条件を満たす立体を作れるか否か、求めよ。
　

解法

　座標 に関して、 の内一つでも 'N' があれば に単位立方体を配置することはできません。従って単位立方体を配置できる座標とは、 が全て 'Y' であるような座標です。射影に関する条件にだけ着目すると、このような座標には自由に単位立方体を配置することができます。しかし、置ける位置全てに単位立方体を配置してしまうと、連結成分が 2 つ以上できてしまうケースが存在するため、これだけでは足りません。
　連結成分の数を 1 つ以下に抑える方法を考えます。さて、配置可能な位置の集合からなる立体を考えたとき、この立体中の 2 つ以上の連結成分に同時に単位立方体を実際に配置すると、連結性の条件は絶対に満たされません。すなわち、valid な立体に於いて単位立方体が配置されているのは、1 つの連結成分の中だけであると言えます。また、1 つの連結成分の中に限定した上で置ける位置全てに配置する戦略をとったとき、連結性の条件は確実に満たされ、配置不可能な場所に配置してしまうこともありません。ただし、配置しなければならない場所に配置されない（⇔射影したときに影ができなければならない場所に影ができない）可能性があるので、配置したあとに実際に射影してみて、それぞれが と一致するか確かめる必要があります。射影が一致すれば、射影に関する条件も連結性に関する条件も満たされているので、立体をつくることが可能であると分かります。逆に、連結成分を全て試しても一致する射影が得られなければ、不可能です。
　同じ連結成分に属する座標を列挙するのは、DFS などの全探索アルゴリズムを用いることができます。また、射影の構築は、ある座標 に単位立方体が配置されていれば に 'Y' を代入し、それ以外は 'N' とする（初期状態で 'N' を埋めておけば特に処理する必要は無い）ことでできます。また、この処理を連結成分を求める DFS の内部に埋め込むことでコードをまとめられます。
　この解法は、（各座標が高々 1 回だけ探索されるように実装すれば）連結成分の全列挙および射影の構築に 時間かかります。射影の一致判定は 時間でできるので、全体は 時間で完了します。 であるので、時間内に解を出せることを期待できます。

コード

using VI = vector<int>; using VVI = vector<VI>;
using VS = vector<string>;
template < typename T = int > using VT = vector<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

constexpr int dx[] = { 1, -1, 0, 0, 0, 0 };
constexpr int dy[] = { 0, 0, 1, -1, 0, 0 };
constexpr int dz[] = { 0, 0, 0, 0, 1, -1 };

class ShadowSculpture
{
public:
	string possible( vector <string> XY, vector <string> YZ, vector <string> ZX )
	{
		const int N = XY.size();

		VT< VVI > object( N, VVI( N, VI( N ) ) );
		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				REP( k, 0, N )
				{
					object[i][j][k] = XY[i][j] == 'Y' && YZ[j][k] == 'Y' && ZX[k][i] == 'Y';
				}
			}
		}

		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				REP( k, 0, N )
				{
					VS xy( N, string( N, 'N' ) ), yz( xy ), zx( xy );
					dfs( object, xy, yz, zx, i, j, k );
					if ( tie( XY, YZ, ZX ) == tie( xy, yz, zx ) )
					{
						return "Possible";
					}
				}
			}
		}

		return "Impossible";
	}

	void dfs( VT< VVI > &G, VS &xy, VS &yz, VS &zx, const int x, const int y, const int z )
	{
		if ( !G[x][y][z] )
		{
			return;
		}

		G[x][y][z] = 0;
		xy[x][y] = yz[y][z] = zx[z][x] = 'Y';

		REP( d, 0, 6 )
		{
			const int nx = x + dx[d];
			const int ny = y + dy[d];
			const int nz = z + dz[d];

			if ( 0 <= min( { nx, ny, nz } ) && max( { nx, ny, nz } ) < (int)G.size() )
			{
				dfs( G, xy, yz, zx, nx, ny, nz );
			}
		}

		return;
	}
};