0923每日一题

解题思路:深度搜索所有可能，选出最优解

注意事项:
如何进行dfs的回溯和标记管理
参考代码:

#include using namespace std;
int n = 9;
bool flag[10];
int ans[10];//flag进行标记管理，ans进行存储得出的数值 
void dfs(int k)
{
    int a, b, c;
    if(k > n) //判断是不是走到尽头 如果是说明走完了一条路线，进行判断是不是需要的解 
    {
        a = ans[1] * 100 + ans[2] * 10 + ans[3];//因为1-9选出不同的三个数 
        b = ans[4] * 100 + ans[5] * 10 + ans[6];
        c = ans[7] * 100 + ans[8] * 10 + ans[9];
    if(b / 2 == a && c / 3 == a) //判断是不是符合条件的最优解 
        cout << a << " " << b << " " << c << endl;
       return;
    }
    for(int i = 1; i <=n; i ++)  
    {
        if(flag[i] == false)
        {
            ans[k] = i;
            flag[i] = true;//标记i 
            dfs(k + 1);//选择k+1位置的数   //进行下一层搜索 
            flag[i] = false; //取消标记，让后续可以选择这个i
        } 
       }
}
int main()
{
    dfs(1);
    return 0;
}