三羊献瑞

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

观察下面的加法算式：

      祥 瑞 生 辉
  +   三 羊 献 瑞
-------------------
   三 羊 生 瑞 气

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

请你输出“三羊献瑞”所代表的 4 位数字（答案唯一）。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路：

我们可以列出方程，枚举出八个数字的可能。注意，进位尤其重要！！！

代码如下：
 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int arr[10];
int a,b,c,d,e,f,g,h;//对应下标1 2 3 4 5 6 7 8 
bool vis[10];
bool found;
void dfs(int x)
{
    if(found)
    return;
    
    if(arr[1] == 0 || arr[5] == 0)//开头a，e不能为0 
    return;
    
    if(x > 8)
    {
        int k1,k2,k3,k4;
        k1 = k2 = k3 = k4 = 0;
        a = arr[1];
        b = arr[2];
        c = arr[3];
        d = arr[4];
        e = arr[5];
        f = arr[6];    
        g = arr[7];
        h = arr[8];

        k1 = (d+b)/10;
        k2 = (c+g+k1)/10;
        k3 = (b+f+k2)/10;
        k4 = (a+e+k3)/10;
        
        if(h == (d+b)%10 && b == (c+g+k1)%10 && c == (b+f+k2)%10 && f == (a+e+k3)%10 && e == k4)
        {
            found = true;
            cout <<  e  <<  f << g  <<  b ;
        }
        return;
    }
    for(int i = 0 ; i <= 9 ; i++)
    {
        if(vis[i] == false)
        {
            vis[i] = true;
            arr[x] = i;
            dfs(x+1);
            vis[i] = false;
            arr[x] = -1;    
        }
    }
}
int main() 
{
    memset(arr,-1,sizeof(arr)); 
    dfs(1);
    return 0;
}