NERC 2015 Hypercube 题解

NERC 2015 Hypercube 题解

题目意思非常简单。判定一个三维图形能否拼成一个超立方体。不要问我超立方体长啥样

我们回忆一下三维展开怎么做。

假设一个正方体展开图像下面这样：

.......
..e....
.abcd..
..f....
.......

则我们钦定正方体的底面为b，则我们在每一个位置放上一个正方体，然后滚动到b。可以发现那些地面恰好构成一个正方体$Leftrightarrow $底面互不相同。

我们可以尝试用一个三元组来表示一个滚动状态：(a,b,c)，表示在前后，左右，上下方向是哪一个面，根据上下/前后/左右来取正负。钦定一个正方体的前，右，上为A,B,C。则初始状态为((A,B,C))。

向前滚动为((A,-B,C))。。。

这样每一个三元组可以映射到唯一的三元组。

这样也可以扩展到四维。

const int MAXN=10;
int n,m,k;
char C[MAXN][MAXN][MAXN];
map<int,int> M;
bool vis[MAXN][MAXN][MAXN];
void dfs(int x,int y,int z,int a,int b,int c,int d){
	if(vis[x][y][z]) return ;
	vis[x][y][z]=true;
	if(M.find(d)!=M.end()){	
		puts("No");exit(0);
	}
	M[d]=1;
	if(C[x+1][y][z]=='x') dfs(x+1,y,z,d,b,c,-a); 
	if(C[x-1][y][z]=='x') dfs(x-1,y,z,-d,b,c,a);
	if(C[x][y+1][z]=='x') dfs(x,y+1,z,a,d,c,-b);
	if(C[x][y-1][z]=='x') dfs(x,y-1,z,a,-d,c,b);
	if(C[x][y][z+1]=='x') dfs(x,y,z+1,a,b,d,-c);
	if(C[x][y][z-1]=='x') dfs(x,y,z-1,a,b,-d,c);
}
int main(){
	scanf("%d%d%d",&m,&n,&k);
	rb(i,1,k)
		rb(j,1,n)
			rb(l,1,m) cin>>C[i][j][l];
	rb(i,1,k) rb(j,1,n) rb(l,1,m) if(C[i][j][l]=='x'){
		dfs(i,j,l,1,2,3,4);
		puts("Yes");
		return 0;
	}
	return 0;
}