TopCoder SRM 638 Div1 Easy ShadowSculpture

SRM638に参加。
EasyよりMediumの方が正答者が多いという変な回。
自分もEasyは落としたけどなんとかMediumを解いてレートを維持した。
http://community.topcoder.com/stat?c=problem_statement&pm=13355

問題

N*N*Nの立法グリッドのうち、幾つかの連結したセルをブロックを配置してオブジェを作った。
このオブジェを、XY平面・YZ平面・ZX平面それぞれの方向に射影したときの各２次元グリッドにおけるブロックの有無が与えられる。

各射影に合致するようなオブジェは存在するか。

解法

XY平面に射影したとき、２次元グリッド上でブロックがあっても、元のオブジェのうちどのZ座標にブロックがあるかは不明である。
ただし、２次元グリッド上にブロックがない場合、元のオブジェではどのZ座標もブロックがない。
まず上記作業を各平面で実行し、ブロックが存在しない場所を確定させる。

これだけでは元オブジェの形状は確定しない。
なぜなら、３平面の射影がいずれも以下の形状となる場合、上記処理だけでは中央に浮いたブロックが残り非連結なブロックが存在してしまうためである。

YYYYY
YYNYY
YYYYY
YYNYY
YYYYY

よってこのような非連結ブロックを取り除くため、各連結ブロック群において、入力の射影を再現できるものがあるか求めればよい。

class ShadowSculpture {
	public:
	int N;
	int bl[11][11][11];
	int con[11][11][11];
	
	void conn(int sx,int sy,int sz) {
		int x,y,z,i;
		ZERO(con);
		if(bl[sz][sy][sx]==0) return;
		
		queue<int> Q;
		con[sz][sy][sx]=1;
		Q.push(sz*10000+sy*100+sx);
		while(Q.size()) {
			int k=Q.front();
			Q.pop();
			int sz=k/10000,sy=k/100%100,sx=k%100;
			FOR(i,6) {
				int dx[6]={1,-1,0,0,0,0},dy[6]={0,0,1,-1,0,0},dz[6]={0,0,0,0,1,-1};
				int tx=sx+dx[i],ty=sy+dy[i],tz=sz+dz[i];
				if(tx<0 || ty<0 || tx>=N || ty>=N || tz<0 || tz>=N) continue;
				if(bl[tz][ty][tx]==0 || con[tz][ty][tx]) continue;
				con[tz][ty][tx]=1;
				Q.push(tz*10000+ty*100+tx);
			}
		}
	}
	
	string possible(vector <string> XY, vector <string> YZ, vector <string> ZX) {
		string po="Possible";
		string im="Impossible";
		
		int x,y,z,sx,sy,sz;
		N=XY.size();
		
		FOR(y,N) FOR(x,N) FOR(z,N) bl[z][y][x]=1;
		FOR(y,N) FOR(x,N) if(XY[x][y]=='N') FOR(z,N) bl[z][y][x]=0;
		FOR(z,N) FOR(x,N) if(ZX[z][x]=='N') FOR(y,N) bl[z][y][x]=0;
		FOR(z,N) FOR(y,N) if(YZ[y][z]=='N') FOR(x,N) bl[z][y][x]=0;
		
		FOR(sz,N) FOR(sy,N) FOR(sx,N) {
			conn(sx,sy,sz);
			int ok=1;
			FOR(y,N) FOR(x,N) {
				int bll=0;
				FOR(z,N) bll+=bl[z][y][x]&&con[z][y][x];
				if(XY[x][y]=='Y' && bll==0) ok=0;
			}
			FOR(z,N) FOR(x,N) {
				int bll=0;
				FOR(y,N) bll+=bl[z][y][x]&&con[z][y][x];
				if(ZX[z][x]=='Y' && bll==0) ok=0;
			}
			FOR(z,N) FOR(y,N) {
				int bll=0;
				FOR(x,N) bll+=bl[z][y][x]&&con[z][y][x];
				if(YZ[y][z]=='Y' && bll==0) ok=0;
			}
			if(ok) return po;
		}
		
		return im;
	}
}

まとめ

色々コーナーケースが多くて、300ptにしてもキツい問題。