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的人最少的一道题吧)

2 Responses

发表评论

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

Back to Top