问题描述
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 |