题目描述: 奇特的立方体
任意给出 8 个整数, 将这 8 个整数分别放在一个立方体的八个顶点上, 要求检验每个面上的四个数之和相等这个条件能否被满足
输入
一次输入 8 个整数
输出
YES 或者 NO
YES 表示可能构成满足条件的立方体
NO 则表示不能
样例输入
1 2 3 4 5 6 7 8
样例输出
YES
思路: 标记 8 个顶点的位置, 构建子空间树即可重点是计算每个面的顶点和!!!!!
- // 奇特的立方体. cpp : 定义控制台应用程序的入口点
- //
- #include "stdafx.h"#include <iostream> #include < cstring > using namespace std;
- const int MAX = 100;
- int n = 8,
- flag,
- arr[MAX]
- /*8 个数字 */
- ,
- vis[MAX]
- /*8 个位置是否放了 */
- ,
- map[MAX]
- /* 每个位置上方的数字 */
- ;
- void printa() {
- for (int i = 0; i < n; i++) cout << map[i] << " ";
- cout << endl;
- }
- int check() {
- //printa();
- int s[6] = {
- 0
- };
- s[0] = map[0] + map[1] + map[2] + map[3];
- s[1] = map[4] + map[5] + map[6] + map[7];
- s[2] = map[0] + map[1] + map[4] + map[5];
- s[3] = map[2] + map[3] + map[6] + map[7];
- s[4] = map[0] + map[3] + map[4] + map[7];
- s[5] = map[1] + map[2] + map[5] + map[6];
- for (int i = 1; i < 6; i++) {
- if (s[i - 1] != s[i]) return 0;
- }
- //cout << "sum:" << s[0] << endl;
- return 1;
- }
- void DFS(int pos) {
- //cout << "pos:" << pos << endl;
- if (flag) return;
- if (pos >= n) {
- if (check()) {
- flag = 1;
- }
- return;
- }
- for (int i = 0; i < n; i++) {
- if (!vis[i]) {
- vis[i] = 1;
- map[i] = arr[pos];
- DFS(pos + 1);
- vis[i] = 0;
- map[i] = 0;
- }
- }
- }
- int main() {
- for (int i = 0; i < n; i++) cin >> arr[i];
- flag = 0;
- memset(vis, 0, sizeof(vis));
- memset(map, 0, sizeof(map));
- DFS(0);
- if (flag) cout << "YES" << endl;
- else cout << "NO" << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2521992.html