蓝桥杯 [五星填数] 问题

helloxiaoc

解题思路:  求1-12除7, 11的全排列, 问题是在求全排列的过程中会出现重复的数字


标题：五星填数

如【图1.png】的五星图案节点填上数字：1~12，除去7和11。
要求每条直线上数字和相等。

如图就是恰当的填法。

请你利用计算机搜索所有可能的填法有多少种。
注意：旋转或镜像后相同的算同一种填法。

请提交表示方案数目的整数，不要填写任何其它内容。

代码如下

                               
登录/注册后可看大图

#include <iostream>
#include <list>
#define SIZE 10

using namespace std;

// 参与排列的数
int numArray[SIZE] = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12};
// 储存已经排列的数
int nNumber[SIZE] = {0};
// 储存所有排列好的数列
list<int*> listNumber;
static void printStar(int* array)
{
        cout<< "第一条线"<< array[0]<< array[1]<< array[2]<< array[3]<< "\n";
        cout<< "第二条线"<< array[3]<< array[4]<< array[5]<< array[6]<< "\n";
        cout<< "第三条线"<< array[6]<< array[7]<< array[1]<< array[8]<< "\n";
        cout<< "第四条线"<< array[8]<< array[2]<< array[4]<< array[9]<< "\n";
        cout<< "第五条线"<< array[9]<< array[5]<< array[7]<< array[0]<< "\n\n";
}
// 检查array是否包含v
bool repeat(const int *array, int v, int end)
{
        for(int i = 0; i < end; i++)
        {
                if(array[i] == v) return true;
        }
        return false;
}
// 将array元素置于五角星每个顶顶, 判断每条直线上的数字之和是否相等, 相等返回true
bool group(const int* array)
{
        // 五角星五个顶点
        int line[5][4] = {
                {array[0], array[1], array[2], array[3]},
                {array[3], array[4], array[5], array[6]},
                {array[6], array[7], array[1], array[8]},
                {array[8], array[2], array[4], array[9]},
                {array[9], array[5], array[7], array[0]}};
        // 计算第一条线上的和
        int sum = line[0][0] + line[0][1] + line[0][2] + line[0][3];
        for(int i = 1; i < 5; i++)
        {
                // 计算每条线上的和并于第一条线之和进行比较, 不相等则返回false
                int lSum = line[i][0] + line[i][1] + line[i][2] + line[i][3];
                if(sum != lSum) return false;
        }       
        return true;
}
// 检查结果翻转(逆序),旋转(位移)之后是否相等
static bool _count(const int*array, const int* array1)
{
        int i, n, b;
        // 下面是他们组成的五角星点阵
        int line[5][4] = {
                {array[0], array[1], array[2], array[3]},
                {array[3], array[4], array[5], array[6]},
                {array[6], array[7], array[1], array[8]},
                {array[8], array[2], array[4], array[9]},
                {array[9], array[5], array[7], array[0]}},
        line1[5][4] = {
                {array1[0], array1[1], array1[2], array1[3]},
                {array1[3], array1[4], array1[5], array1[6]},
                {array1[6], array1[7], array1[1], array1[8]},
                {array1[8], array1[2], array1[4], array1[9]},
                {array1[9], array1[5], array1[7], array1[0]}};
        // 镜像翻转
        for(i = 0; i < 5; i++)
        {
                for(n = 0; n < 4; n++)
                {
                        if(line[5-i-1][4-n-1] != line1[i][n]) return false;
                }
        }
        // 旋转 (H代表的是旋转的次数)
        for(int H = 0; H < 5; H++)
        {
                b = true;
                for(i = 0; i < 5; i++)
                {
                        for(n = 0; n < 4; n++)
                        {
                                if(line[(H+i)%5][n] != line1[i][n])
                                {
                                        b = false;
                                        break;
                                }
                        }
                        if(!b) break;
                }
                if(b) return true;
        }
        if(!b) return false;
        return true;
}
// 检查重复, 有重复返回true
bool count(const int* array)
{
        list<int*>::iterator iter;
        for(iter = listNumber.begin(); iter != listNumber.end(); iter++)
        {
                if(_count(array, *iter)) return true;
        }
        return false;
}
// 将array1复制到array中
int* toArray(int* array, const int* array1)
{
        for(int i = 0; i < SIZE; i++)
        {
                array[i] = array1[i];
        }
        return array;
}
// dfs求numArray的全排列, 参数是当前所在位置
void dfs(int pos)
{
        if(pos >= SIZE)
        {
                // 每条线不相等则返回
                if(!group(nNumber)) return;
                // 每条线相等但是翻转或旋转之后在listNumber中能找到对应的数列则返回
                if(count(nNumber)) return;
                // 将nNumber添加到list中
                listNumber.push_back(toArray(new int(SIZE), nNumber));
                printStar(nNumber);
                return;
        }
        for(int i = 0; i < SIZE; i++)
        {
                for(int n = 0; n < pos; n++) cout<< nNumber[n];
                cout<< "x"<< pos<< "----\n";
                // 检查重复
                if(repeat(nNumber, numArray[i], pos)) continue;
                nNumber[pos] = numArray[i];
                dfs(pos+1);
        }
}

int main(int argc, char* argv[])
{
        dfs(0);
        cout<< listNumber.size();
       
        return 0;
}

零度冷咖啡

我是第一个？虽然我看不懂

helloxiaoc

零度冷咖啡 发表于 2019-1-27 20:22
我是第一个？虽然我看不懂

抄袭了一下网上的答案, 突然感觉好简单..