Ela's Notes
So Be It


Hitokoto ·
dfs求解网上的一份推理题
Elatis   算法, C++   609 | 文章字数: 6196 字

搬运自旧站,最近没什么心情写文章呢

就是这份

源码如下:(懒得写注释)

/**
 * 思路:
 * 1.使用深搜枚举答案
 * 2.根据枚举出来的答案,推出各题答案,并与枚举出来的答案比对
 * 3.如果完全符合,就输出
 */
#include <algorithm>
#include <iostream>
#define maxn 0x3f3f3f3f
using namespace std;

const string go = "ABCD";

struct node_q7
{
    int value;
    char no;

    bool operator==(const node_q7 other) const
    {
        return this->value == other.value;
    }

    bool operator<(const node_q7 other) const
    {
        return this->value < other.value;
    }
};

bool judge(string ans)
{

    //第二题
    char ans_of_q2;
    switch (ans[4]) //根据第五题的答案来推第二题的答案
    {
    case 'A':
        ans_of_q2 = 'C';
        break;
    case 'B':
        ans_of_q2 = 'D';
        break;
    case 'C':
        ans_of_q2 = 'A';
        break;
    case 'D':
        ans_of_q2 = 'B';
    }
    if (ans_of_q2 != ans[1])
        return false;

    //第三题
    char ans_of_q3 = 0;
    char temp_q3[4];
    temp_q3[0] = ans[2];
    temp_q3[1] = ans[5];
    temp_q3[2] = ans[1];
    temp_q3[3] = ans[3];
    int cnt_q3;
    for (int i = 0; i < 4; ++i)
    {
        cnt_q3 = 0;
        for (int j = 0; j < 4; ++j)
        {
            if (temp_q3[i] != temp_q3[j])
                ++cnt_q3;
        }
        if (cnt_q3 == 3)
        {
            if (ans_of_q3 == 0)
            {
                ans_of_q3 = ('A' + i);
            }
            else
            {
                return false;
            }
        }
        else if (cnt_q3 > 1 || cnt_q3 == 0)
        {
            return false;
        }
    }
    if (ans_of_q3 != ans[2])
        return false;

    //第四题
    char ans_of_q4 = 0;
    if (ans[0] == ans[4])
        ans_of_q4 = 'A';
    if (ans[1] == ans[6])
    {
        if (ans_of_q4)
            return false;
        ans_of_q4 = 'B';
    }
    if (ans[0] == ans[8])
    {
        if (ans_of_q4)
            return false;
        ans_of_q4 = 'C';
    }
    if (ans[5] == ans[9])
    {
        if (ans_of_q4)
            return false;
        ans_of_q4 = 'D';
    }
    if (ans_of_q4 != ans[3])
        return false;

    //第五题
    char ans_of_q5 = 0;
    if (ans[7] == ans[4])
        ans_of_q5 = 'A';
    if (ans[3] == ans[4])
    {
        if (ans_of_q5)
            return false;
        ans_of_q5 = 'B';
    }
    if (ans[8] == ans[4])
    {
        if (ans_of_q5)
            return false;
        ans_of_q5 = 'C';
    }
    if (ans[6] == ans[4])
    {
        if (ans_of_q5)
            return false;
        ans_of_q5 = 'D';
    }
    if (ans_of_q5 != ans[4])
        return false;

    //第六题
    char ans_of_q6 = 0;
    if (ans[1] == ans[4])
    {
        if (ans[1] == ans[7])
            ans_of_q6 = 'A';
    }
    if (ans[0] == ans[5])
    {
        if (ans[0] == ans[7])
        {
            if (ans_of_q6)
                return false;
            ans_of_q6 = 'B';
        }
    }
    if (ans[2] == ans[9])
    {
        if (ans[2] == ans[7])
        {
            if (ans_of_q6)
                return false;
            ans_of_q6 = 'C';
        }
    }
    if (ans[4] == ans[8])
    {
        if (ans[4] == ans[7])
        {
            if (ans_of_q6)
                return false;
            ans_of_q6 = 'D';
        }
    }
    if (ans_of_q6 != ans[5])
        return false;

    //第七题
    char ans_of_q7;
    node_q7 cnt_q7[4];
    for (int i = 0; i < 4; ++i)
    {
        cnt_q7[i].value = 0;
        cnt_q7[i].no = ('A' + i);
    }

    for (int i = 0; i < 10; ++i)
    {
        ++cnt_q7[(ans[i] - 'A')].value;
    }
    sort(cnt_q7, cnt_q7 + 4);
    if (cnt_q7[0] == cnt_q7[1])
        return false;
    ans_of_q7 = cnt_q7[0].no;
    if (ans_of_q7 != ans[6])
        return false;

    //第八题
    char ans_of_q8 = 0;
    if (ans[6] != (ans[0] - 1) && ans[6] != (ans[0] + 1))
    {
        ans_of_q8 = 'A';
    }
    if (ans[4] != (ans[0] - 1) && ans[4] != (ans[0] + 1))
    {
        if (ans_of_q8)
            return false;
        ans_of_q8 = 'B';
    }
    if (ans[1] != (ans[0] - 1) && ans[1] != (ans[0] + 1))
    {
        if (ans_of_q8)
            return false;
        ans_of_q8 = 'C';
    }
    if (ans[9] != (ans[0] - 1) && ans[9] != (ans[0] + 1))
    {
        if (ans_of_q8)
            return false;
        ans_of_q8 = 'D';
    }
    if (ans_of_q8 != ans[7])
        return false;

    //第十题
    char ans_of_q10;
    switch (cnt_q7[3].value - cnt_q7[0].value)
    {
    case 3:
        ans_of_q10 = 'A';
        break;
    case 2:
        ans_of_q10 = 'B';
        break;
    case 4:
        ans_of_q10 = 'C';
        break;
    case 1:
        ans_of_q10 = 'D';
        break;
    default:
        return false;
    }
    if (ans_of_q10 != ans[9])
        return false;

    //第九题
    char ans_of_q9 = 0;
    bool flag_q9 = (ans[0] == ans[5]);
    if (flag_q9 != (ans[5] == ans[4]))
        ans_of_q9 = 'A';
    if (flag_q9 != (ans[9] == ans[4]))
    {
        if (ans_of_q9)
            return false;
        ans_of_q9 = 'B';
    }
    if (flag_q9 != (ans[1] == ans[4]))
    {
        if (ans_of_q9)
            return false;
        ans_of_q9 = 'C';
    }
    if (flag_q9 != (ans[8] == ans[4]))
    {
        if (ans_of_q9)
            return false;
        ans_of_q9 = 'D';
    }
    if (ans_of_q9 != ans[8])
        return false;
    return true;
}

void dfs(string ans)
{
    if (ans.length() == 10)
    {
        if (judge(ans))
        {
            for (int i = 0; i < 10; ++i)
            {
                cout << "question " << (i + 1) << ": " << ans[i] << endl;
            }
        }
        return;
    }

    string temp;
    for (int i = 0; i <= 3; ++i)
    {
        temp = ans + go[i];
        dfs(temp);
    }
}

int main()
{
    dfs("");
    getchar();
}

运行结果:

question 1: B
question 2: C
question 3: A
question 4: C
question 5: A
question 6: C
question 7: D
question 8: A
question 9: B
question 10: A

评论

发送失败 可能是您的发言太频繁或联系方式有误

提交评论

Theme LightWhite Made by Archeb With
自豪地使用Typecho
© 2017 - 2019 Ela's Notes 全站共 19.96 W 字
博客已经运行了