8-5 連環の数 初級編

問題

連なった円の中に1から始まる、連続した自然数を入れていきます。
ただし、円の重なった部分には、その左右に入っている数の和を入れてください

円が２つの場合は1から3の数が図のように入ります。


円が3つの場合は、1から5の数が、例えば図のように入ります。


円が4個の場合、1から7までの数を入れてみてください

ソース

#include <stdio.h>
#include <Windows.h>
#include <stack>
#include <algorithm>

const int CircleCnt = 4;
const int MaxVal = CircleCnt * 2 - 1;

struct JyoutaiDef
{
    int Level;
    int IntArr[MaxVal];
};

bool IsValid(JyoutaiDef pJyoutai);
bool IsValidHelper(int pArr[],int P1,int P2,int P3);

void main()
{
    std::stack<JyoutaiDef> stk;
    JyoutaiDef WillPush;
    ZeroMemory(WillPush.IntArr,sizeof(WillPush.IntArr));
    WillPush.Level = 1;

    for (int I = 1; I <= MaxVal; I++) {
        WillPush.IntArr[0] = I;
        stk.push(WillPush);
    }

    int AnswerCnt = 0;
    while (stk.empty() == false) {
        JyoutaiDef Popped = stk.top(); stk.pop();

        if (Popped.Level == MaxVal) {
            char WillOut[256] = {'\0'};
            for(int I=0;I<=sizeof(Popped.IntArr)/sizeof(int)-1;I++){
                char wk[99];wsprintf(wk,"%d,",Popped.IntArr[I]);
                strcat_s(WillOut,wk);
            }
            printf("answer%d = %s\n", ++AnswerCnt,WillOut);
            continue;
        }

        WillPush.Level = Popped.Level + 1;

        for (int I = 1; I <= MaxVal; I++) {
            if (std::count(Popped.IntArr,Popped.IntArr+sizeof(Popped.IntArr)/sizeof(int),I)>0)
                continue;

            memcpy(WillPush.IntArr,Popped.IntArr,sizeof(Popped.IntArr));
            WillPush.IntArr[WillPush.Level - 1] = I;

            if (IsValid(WillPush)) stk.push(WillPush);
        }
    }
}

bool IsValid(JyoutaiDef pJyoutai)
{
    if (CircleCnt >= 2) {
        if (IsValidHelper(pJyoutai.IntArr, 0, 1, 2) == false) return
            false;
    }
    if (CircleCnt >= 3) {
        if (IsValidHelper(pJyoutai.IntArr, 2, 3, 4) == false) return
            false;
    }
    if (CircleCnt >= 4) {
        if (IsValidHelper(pJyoutai.IntArr, 4, 5, 6) == false) return
            false;
    }
    return true;
}

bool IsValidHelper(int pArr[],int P1,int P2,int P3)
{
    if (pArr[P1] != 0 && pArr[P2] != 0 && pArr[P3] != 0) {
        if (pArr[P2] != pArr[P1] + pArr[P3]) return false;
    }
    return true;
}

実行結果

answer1 = 6,7,1,4,3,5,2,
answer2 = 3,4,1,6,5,7,2,
answer3 = 2,7,5,6,1,4,3,
answer4 = 2,5,3,4,1,7,6,

解説

std::countアルゴリズムは便利ですね。
MSDN --- std::count