【深度优先搜索】练习题：填数字

vlambda
2020-08-02

【深度优先搜索】练习题：填数字

填数字

这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。

比如：

6+8/3+952/714就是一种解法，

这个算式一共有多少种解法？

b def

a + - + --- = 10

c ghi

输出

输出一个整数，表示算式的解的总数。

答案：

#include <iostream>using namespace std;
int a[11],cnt;bool b[11];void dfs(int step){ if(step == 10 ) { float sum1 = a[2]; float sum2 = a[4] * 100 + a[5] * 10 + a[6]; float sum3 = a[7] * 100 + a[8] * 10 + a[9]; if(a[1] + sum1 / a[3] + sum2 / sum3 == 10)        { cnt++; } return; } for(int i = 1;i<=9;i++) { if(b[i] == 0) { a[step] = i; b[i] = 1; dfs(step + 1); b[i] = 0; } }}int main(){ dfs(1); cout<<cnt; return 0;}