HDU 6657 – Acesrc and Cube Hypernet

题意：给一个纸条，问是否可以折成一个立方体，纸条用一个h*w的矩阵上的’#’来描述，h<=100，w<=100，T<=30（数据组数）。

分析：当时多校赛场上读完题就想到了可以枚举点然后BFS填充格子，只要有一个起点能满足不重复地填充给出图形上的所有’#’号点，且立方体被填满，就输出yes。由于h<=100,w<=100，所以最大的正方体的边长为100/4=25，因此我们枚举点25*25，check使用25*25*6的复杂度可以完成。

不过因为后来跟榜先搞别的题去了这题就先放一边，结果我们队后来因为开车那题自闭到最后。

这题的难点在于处理BFS时转向的问题。

我们可以先建立一个三维坐标，第一维是所属的面，第二维和第三维是这个坐标在这个面中的位置。如下图所示，中间的数字是面坐标的编号。

然后对于编号1的面，向周围4个面走的时候都是直接走即可，不需要进行坐标变换。

而对于需要进行坐标变换的情况，比如从0这个面一直向上走，走到4，需要将x和y坐标对调，然后逆时针转90°，再继续填充这个格子。

对于6个面，向4个方向走只有6*4=24种情况，所以直接把这24种情况x和y和方向的变化写出来（可以用if或者switch），然后直接做就完了。

然后就直接上一段很丑的代码吧。（为什么这么丑还要写博客呢，因为这算是在多校期间补的题中AC的人最少的一道题吧）

#include <bits/stdc++.h>
using namespace std;
int sz;
int trans(int &x,int &y,int &deg,int from) {//x和y是这个点在该面的坐标，from是当前面的编号，返回移动之后面的编号
	if (from == 0) {
		if (y == sz + 1) {
			y = 1;
			return 1;
		}
		else if (y == 0) {
			y = sz;
			return 3;
		}
		else if (x == 0) {
			x = y;
			y = 1;
			deg = (deg - 1 + 4) % 4;
			return 5;
		}
		else if (x == sz + 1) {
			x = sz - y + 1;
			y = 1;
			deg = (deg + 1 + 4) % 4;
			return 4;
		}
	}
	else if (from == 1) {
		if (x == 0) {
			x = sz;
			return 5;
		}
		else if (x == sz + 1) {
			x = 1;
			return 4;
		}
		else if (y == 0) {
			y = sz;
			return 0;
		}
		else if (y == sz + 1) {
			y = 1;
			return 2;
		}
	}
	else if (from == 2) {
		if (y == 0) {
			y = sz;
			return 1;
		}
		else if (y == sz + 1) {
			y = 1;
			return 3;
		}
		else if (x == 0) {
			x = sz - y + 1;
			y = sz;
			deg = (deg + 1 + 4) % 4;
			return 5;
		}
		else if (x == sz + 1) {
			x = y;
			y = sz;
			deg = (deg - 1 + 4) % 4;
			return 4;
		}
	}
	else if (from == 3) {
		if (y == 0) {
			y = sz;
			return 2;
		}
		else if (y == sz + 1) {
			y = 1;
			return 0;
		}
		else if (x == 0) {
			y = sz + 1 - y;
			x = 1;
			deg = (deg + 2 + 4) % 4;
			return 5;
		}
		else if (x == sz + 1) {
			y = sz + 1 - y;
			x = sz;
			deg = (deg - 2 + 4) % 4;
			return 4;
		}
	}
	else if (from == 4) {
		if (x == 0) {
			x = sz;
			return 1;
		}
		else if (x == sz + 1) {
			x = sz;
			y = sz + 1 - y;
			deg = (deg + 2 + 4) % 4;
			return 3;
		}
		else if (y == 0) {
			y = sz - x + 1;
			x = sz;
			deg = (deg - 1 + 4) % 4;
			return 0;
		}
		else if (y == sz + 1) {
			y = x;
			x = sz;
			deg = (deg + 1 + 4) % 4;
			return 2;
		}
	}
	else if (from == 5) {
		if (x == sz + 1) {
			x = 1;
			return 1;
		}
		else if (x == 0) {
			x = 1;
			y = sz - y + 1;
			deg = (deg - 2 + 4) % 4;
			return 3;
		}
		else if (y == 0) {
			y = x;
			x = 1;
			deg = (deg + 1 + 4) % 4;
			return 0;
		}
		else if (y == sz + 1) {
			y = sz - x + 1;
			x = 1;
			deg = (deg - 1 + 4) % 4;
			return 2;
		}
	}
	return -1;
}
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
char s[105][105];
bool vis[105][105];
bool vis2[6][105][105];
int h,w,si,sj;
struct DATA {
	int i,j,x,y,z,dir;
};
bool check(int x,int y) {
	memset(vis,0,sizeof(vis));
	memset(vis2,0,sizeof(vis2));
	vis[si][sj] = true;
	queue <DATA> q;
	q.push({si,sj,x,y,0,0});
	vis2[0][x][y] = true;
	int cnt = 0;
	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		cnt ++;
		for (int d=0;d<4;d++) {
			int ni = cur.i + dx[d];
			int nj = cur.j + dy[d];
			if (ni < 1 || nj < 1 || ni > h || nj > w || s[ni][nj] != '#' || vis[ni][nj]) continue;
			vis[ni][nj] = true;
			int nx = cur.x + dx[(d+cur.dir)%4];
			int ny = cur.y + dy[(d+cur.dir)%4];
			int nz = cur.z;
			int ndir = cur.dir;
			if (nx == 0 || ny == 0 || nx == sz + 1 || ny == sz + 1) nz = trans(nx,ny,ndir,cur.z);
			if (vis2[nz][nx][ny]) continue;
			vis2[nz][nx][ny] = true;
			q.push({ni,nj,nx,ny,nz,ndir});
		}
	}
	return cnt == sz * sz * 6;
}
int main() {
	int T;
	scanf("%d",&T);
	while (T --) {
		scanf("%d%d",&h,&w);
		int cnt = 0;
		for (int i=1;i<=h;i++) {
			scanf("%s",&s[i][1]);
			for (int j=1;j<=w;j++) {
				if (s[i][j] == '#') {
					cnt ++;
					si = i;
					sj = j;
				}
			}
		}
		sz = sqrt(cnt / 6) + 0.5;
		if (sz * sz * 6 == cnt) {
			bool ans = false;
			for (int i=1;i<=sz && !ans;i++) for (int j=1;j<=sz && !ans;j++) {
				if (check(i,j)) ans = true;
			}
			if (ans) printf("yes\n");
			else printf("no\n");
		}
		else printf("no\n");
	}
	return 0;
}