2015蓝桥杯B组第三题（三羊献瑞）

三羊献瑞

观察下面的加法算式：

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。

请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

个人用的DFS搜索，在0~9是个数字中搜索8个数字来满足题目中要求的算式条件，最有去掉开头和第五位为0的情况，相比8重for循环效率还是挺快的，下面附上个人渣代码。

#include <iostream>

using namespace std;

int idx[10] = {false};
int n[8] = {0};

void solve()
{
int res = n[0]*1000 + n[1]*100 + n[2]*10 + n[3] + n[4]*1000 + n[5]*100 + n[6]*10 + n[1];
int res2 = n[4]*10000 + n[5]*1000 + n[2]*100 + n[1]*10 + n[7];
if (res == res2 && n[0] != 0 && n[4] != 0)
    {
for (int i = 0; i < 8; i++)
        {
cout<<n[i]<<" ";
        }
cout<<endl;
    }
}

void dfs(int i, int k)
{
if (k <= 0 || k >= 9)
    {
return ;
    }

    idx[i] = true;
    n[k-1] = i;

if (k == 8)
    {
        solve();
return ;
    }

for (int x = 0; x <= 9; x++)
    {
if (idx[x] == false)
        {
            idx[x] = true;
            dfs(x, k+1);
            idx[x] = false;
        }
    }
}

int main()
{
for (int i = 0; i <= 9; i++)
    {
        idx[i] = true;
        dfs(i, 1);
        idx[i] = false;
    }


return 0;
}