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;
}

5 Responses

  1. 很多预言都讲了会有大瘟疫流行以及各种天灾。不管会不会发生,我们宁可信其有,不可信其无。那么,遇到地震、瘟疫等,应该怎么办呢?得救的人一定良知尚存。
    善良的朋友:
    法 轮 功是佛 家上乘修 炼大 法,原则是真 善 忍。大法可归正人类道德,救度众生于水火。但中共江 氏集团出于嫉恨,火烧活人,自导自演了“天安 门 自 焚”,从而迫害法 轮 功,妄图阻碍众生得救。

  2. 有人说,信神就信神,不信神就不信神,何必争呢,不就是一个信仰问题吗。是信仰,但很重要,因为它既关系到人的幸福和不幸,又关系到人能否在劫难中被救度的问题。
    当人不信神,不相信善恶有报,不再被道德约束时,人会为满足私欲而无恶不作。你看当今人类社会道德急下,人人为近敌,灭门杀人、恐怖袭击,瘟疫和各种灾祸每天都能见到,黄、赌、毒、性开放、同性恋等泛滥成灾,这离《圣经启示录》所预言的世界末日和最后的审判还远吗?
    神许诺人类有劫难时神会来救人。谁来救度?又谁能得救呢?

ecnu996er进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注

Back to Top