荒芜知地

Knowhere

0%

还原魔方-二阶

发表于 分类于 Valine：

还原魔方 - 二阶

问题描述

有一个二阶魔方，即 2×2×2 的一个立方体组。立方体由八个角组成。
魔方的每一块都用三维坐标(h, k, l)标记，其中 h, k, l∈{0,1}。六个面的每一个都有四个小面，每个小面都有一个正整数。
对于每一步，可以选择一个特定的面，并把此面顺时针或逆时针转90度。
请你判断，是否可以在一个步骤还原这个魔方。

Input

输入的第一行包含一个整数N（N ≤ 30），这是测试用例的数量。
对于每个测试用例， 第 1~4 个数描述魔方的顶面，这是常见的2×2面，由（0，0，1），（0，1，1），（1，0，1），（1，1，1）标记。四个整数对应于上述部分。

第 5~8 个数描述前面，即（1，0，1），（1，1，1），（1，0，0），（1，1，0）的公共面。四个整数 与上述各部分相对应。

第 9~12 个数描述底面，即（1，0，0），（1，1，0），（0，0，0），（0，1，0）的公共面。四个整数与上述各部分相对应。

第 13~16 个数描述背面，即（0，0，0），（0，1，0），（0，0，1），（0，1），（0，1，1）的公共面。四个整数与上述各部分相对应。

第 17~20 个数描述左面，即（0，0，0），（0，0，1），（1，0，0），（1，0，1）的公共面。给出四个整数与上述各部分相对应。

第 21~24 个数描述了右面，即（0，1，1），（0，1，0），（1，1，1），（1，1，0）的公共面。给出四个整数与上述各部分相对应。

换句话说，每个测试用例包含24个整数a、b、c到x。你可以展开表面以获得平面图, 如下所示。
+ - + - + - + - + - + - +
| q | r | a | b | u | v |
+ - + - + - + - + - + - +
| s | t | c | d | w | x |
+ - + - + - + - + - + - +
        | e | f |
        + - + - +
        | g | h |
        + - + - +
        | i | j |
        + - + - +
        | k | l |
        + - + - +
        | m | n |
        + - + - +
        | o | p |
        + - + - +

Output

对于每个测试用例，魔方如果可以 "只转一步" 恢复，输出YES，则输出NO。

Sample

Input: 
4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
6 6 6 6 1 1 1 1 2 2 2 2 3 3 3 3 5 5 5 5 4 4 4 4
1 4 1 4 2 1 2 1 3 2 3 2 4 3 4 3 5 5 5 5 6 6 6 6
1 3 1 3 2 4 2 4 3 1 3 1 4 2 4 2 5 5 5 5 6 6 6 6

Output: 
YES
YES
YES
NO

Limitation

Time limit      1000 ms
Memory limit    65536 kb

解题思路

二阶的，而且只需要转一次或不转，相比三阶还算是比较好做。折出一个魔方，观察每一转的字母，可以分割成6转：

cube1.png

即：

a c e g i k m o
b d f h j l n p
l k q r a b u v
j i s t c d w x
r t e f w u p o
q s g h x v n m

录入的时候把这6个数组都录入，由于最多旋转一次，所以无需担心旋转的时候由于一个数组的改变而影响其他数组。

旋转只需判断顺时针(+2)%8，逆时针(+6)%8，或者不转，判断各面颜色即可。

源代码

#include <iostream>
#include <string>
using namespace std;

bool sameC(int arr[2][8]) {
	bool sam[3][8] = { false };
	for (int i = 0; i < 8; i++) {
		if (arr[0][i] == arr[1][i])
			sam[0][i] = true;
		if (arr[0][i] == arr[1][(i + 2) % 8])
			sam[1][i] = true;
		if (arr[0][i] == arr[1][(i + 6) % 8])
			sam[2][i] = true;
	}
	bool sam2[3] = { true, true, true };
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 8; j++)
			if (!sam[i][j])
				sam2[i] = false;
	if (sam2[0] || sam2[1] || sam2[2])
		return true;
	return false;
}

bool solve(int* data) {
	//1: a c e g i k m o;   b d f h j l n p
	//2: l k q r a b u v;   j i s t c d w x
	//3: r t e f w u p o;   q s g h x v n m
	int c1[2][8] = { {0, 2, 4, 6, 8, 10, 12, 14}, {1, 3, 5, 7, 9, 11, 13, 15} };
	int c2[2][8] = { {11, 10, 16, 17, 0, 1, 20, 21}, {9, 8, 18, 19, 2, 3, 22, 23} };
	int c3[2][8] = { {17, 19, 4, 5, 22, 20, 15, 14}, {16, 18, 6, 7, 23, 21, 13, 12} };
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 8; j++) {
			c1[i][j] = data[c1[i][j]];
			c2[i][j] = data[c2[i][j]];
			c3[i][j] = data[c3[i][j]];
		}
	}
	bool sameColor = false;
	if (sameC(c1) && sameC(c2) && sameC(c3))
		sameColor = true;
	
	return sameColor;
}

int main() {
	int N;
	cin >> N;
	while (N--) {
		int data[26];
		for (int i = 0; i < 24; i++)
			cin >> data[i];
		bool res = solve(data);
		if (res)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

原题链接🔗

Pocket Cube