2016年蓝桥杯A组 第六题 寒假作业

今年的题不知为什么，第三道是考的dfs，这第六道同样是考的dfs，看来深度优先遍历是需要好好学学的！

寒假作业

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

□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □

(如果显示不出来，可以参见【图1.jpg】)

每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

就算两种解法。（加法，乘法交换律后算不同的方案）

你一共找到了多少种方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

这里我们很直观就可以想到用dfs，所以就不多分析了，直接上代码了，感觉通过这两道题，让我对dfs的感觉更到位了！

对，就是这个赶脚！跟着赶脚走，学算法是很快的，哈哈哈！

#include <stdio.h>
#define _MAX 13

int ans = 0;
int num[_MAX] = {
  0};
int visited[_MAX] = {
  0};

int test(int n)
{
    if (n == 2)
    {
        if (num[0] + num[1] == num[2])
        {
            return 1;
        }
    }
    else if (n == 5)
    {
        if (num[3] - num[4] == num[5])
        {
            return 1;
        }
    }
    else if (n == 8)
    {
        if (num[6] * num[7] == num[8])
        {
            return 1;
        }
    }
    else if (n == 11)
    {
        if (num[10] * num[11] == num[9])
        {
            ans++;
            return 1;
        }
    }
    else
    {
        return 1;
    }
    return 0;
}

void dfs(int n)
{
    int i = 0;
    if (n >= _MAX)
    {
        return ;
    }
    for (; i < _MAX; i++)
    {
        if (!visited[i])
        {
            visited[i] = 1;
            num[n] = i + 1;
            if (!test(n))   //如果不符合规则，则撤销这个分支
            {
                visited[i] = 0;
                continue;
            }
            dfs(n + 1);
            visited[i] = 0;
        }
    }
    return ;
}

int main(int argc, const char * argv[])
{
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

OVER！！！