深度优先搜索dfs

hrlsm 2020-03-31 原文

题目大意：你手中有编号1-9的九张扑克牌，然后将这9张扑克牌放到9个盒子里，并使得_ _ _+_ _ _=_ _ _成立；

其实就是判断下 a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9] 这个等式是否成立；

用于对dfs的初步学习，希望对你有用；

代码如下：

#include<iostream>
using namespace std;
int a[10],book[10],total=0;
void  dfs(int step)//step表示现在站在第几个盒子面前
{
    int i;
    if(step==10)//如果站在第10个盒子面前，则表示前9个盒子已经放好扑克牌
    {//处理边界问题 
        //判断是否满足等式
        if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
    {
        total++;
        cout<<a[1]<<a[2]<<a[3]<<"+"<<a[4]<<a[5]<<a[6]<<"="<<a[7]<<a[8]<<a[9]<<endl;
    }
        return;//返回之前的一步(最近调用的地方)
    }
    //此时站在第step个盒子面前，应该放哪张牌呢？
    //按照1,2,3,........,n的顺序一一尝试
    for(i=1;i<=9;i++){
        //先判断扑克牌是否还在手上
        if(book[i]==0)//book[i]为0表示扑克牌还在手上
        {
            //开始尝试使用扑克牌
            a[step]=i;//将扑克牌放到第step个盒子里 
            book[i]=1; //将book[i]的值设为1，表示扑克牌i已不在手上
            //第step个盒子已经放置好扑克牌，走到下一个盒子面前
            dfs(step+1);//这里通过函数的递归调用来实现(自己调用自己)
            //这里是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
            book[i]=0; 
         } 
    } 
    return;     
    }
int main()
{
    dfs(1);//首先站在一个盒子面前
    cout<<total/2<<endl;
    getchar();
    getchar();
    return 0;
}