寒假作业---蓝桥杯---DFS

题目描述

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：

每个方块代表1~13中的某一个数字，但不能重复。
比如：

以及：

就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？

答案：64

 

#include<iostream>

#include<string>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

double a[][];

int vis[];

int ans=;

int check(int x,int y,int num)

{

    if(x==&&y<)

        return ;

    if(x==&&y==)

    {

        if(a[][]+a[][]==num)

            return ;

        else

            return ;

    }

    if(x==&&y<)

        return ;

    if(x==&&y==)

    {

        if(a[][]-a[][]==num)

            return ;

        else

            return ;

    }

    if(x==&&y<)

        return ;

    if(x==&&y==)

    {

        if(a[][]*a[][]==num)

            return ;

        else

            return ;

    }

    if(x==&&y<)

        return ;

    if(x==&&y==)

    {

        if(a[][]/a[][]==num)//-------注意除法的时候要用double，否则会多算好多

            return ;

        else

            return ;

    }

    return ;

}

void dfs(int x,int y)

{

    if(x==)

    {

        ans++;

        // for(int i=0;i<4;i++)

        // {

        //     for(int j=0;j<3;j++)

        //         cout<<a[i][j]<<' ';

        //     cout<<endl;

        // }

        return ;

    }

    if(y>=)

        dfs(x+,);

    for(int i=;i<=;i++)

    {

        if(vis[i]==&&check(x,y,i))

        {

            a[x][y]=i;

            vis[i]=;

            dfs(x,y+);

            vis[i]=;

        }

    }

}

int main()

{

    memset(vis,,sizeof(vis));

    dfs(,);

    cout<<ans<<endl;

    return ;

}