问题描述
p253原题链接：UVaOJ 253 - Cube painting
相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-4
解法一：找规律（思维）
朴素解法是将正方体的 24 种摆放姿势生成（或罗列）出来，比如每次固定上下两个面（有六种情况），然后水平旋转 4 次，就能得到全部的可能，然后看是否有匹配的编码，有则输出 "YES".
实际上发现规律就很简单，如果两个正方体可以通过旋转得到，那么它们的 3 个对立面一定能够匹配。这个规律在尝试固定上下两个面的时候就能够发现，不论你选择哪两个面固定，它们一定是相对的，这个相对性在旋转时是不会被打破的。而如果给出了一个正方体的三个相对面，这个正方体其实就被确定了（任意的一个顶点一定与三个面相邻）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <bits/stdc++.h> using namespace std; int main() { string s; while (cin >> s) { vector<pair<char, char>> opposite[2]; for (int i = 0; i < 2; ++i) { int p = 6 * i; opposite[i].push_back(pair<char, char>{s[p], s[p + 5]}); opposite[i].push_back(pair<char, char>{s[p + 1], s[p + 4]}); opposite[i].push_back(pair<char, char>{s[p + 2], s[p + 3]}); } for (auto o : opposite[0]) for (auto it = opposite[1].begin(); it != opposite[1].end(); ++it) if ((o.first == it->first && o.second == it->second) || (o.first == it->second && o.second == it->first)) { opposite[1].erase(it); break; } cout << (opposite[1].empty() ? "TRUE" : "FALSE") << endl; } return 0; } |
|
1 |
#TODO |
