使用DFS求解“24点游戏算法”

1.题目

问题描述：
给出4个1-10的数字，通过加减乘除，得到数字为24就算胜利
输入：
4个1-10的数字。[数字允许重复，但每个数字仅允许使用一次，测试用例保证无异常数字]
输出：
true or false

示例：
输入：

7 2 1 10

输出

true

2.思路精要：

• （1）依次选择n[0],n[1],n[2],n[3]作为顶点。
• （2）某次遍历后，如果最后节点的值为24则返回true，否则回溯。
• （3）所有遍历后均得不到24，返回false。

3. 该题的图到底长什么样呢？

经过分析，如下图所示：

注意；图中的标注为各个顶点的初始值，遍历过程中顶点的值会发生变化。如按加法且路径为左上角-->右上角-->右下角-->左下角，则左下角顶点的值为n[0]+n[1]+n[2]+n[3]。因此，一次遍历后，最后节点的值等于24，就意味着可以得到24。

4.具体代码

// package org.jzy.huawei108;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 初始化数字数组和标志数组
            int[] nums = new int[4];
            int[] signs = new int[4];
            for (int i = 0; i < nums.length; i++) {
                nums[i] = scanner.nextInt();
            }

            boolean can = false; // 是否能得到24
            for (int i = 0; i < nums.length; i++) {
                signs[i] = 1;
                if (dfs(nums, signs, nums[i], 24)) {
                    can = true;
                    break;
                }
                signs[i] = 0;
            }
            System.out.println(can);// 输出结果
        }
    }

    /**
     * 深度优先算法逻辑
     *
     * @param nums     输入的4个数字
     * @param signs    访问标志数组
     * @param v        顶点的值
     * @param required 需要通过四则运算得到的数字
     * @return
     */
    private static boolean dfs(int[] nums, int[] signs, int v, int required) {
        boolean allVisited = true;// 四个角均被访问
        for (int sign : signs) {
            if (sign == 0) {
                allVisited = false;
            }
        }

        if (allVisited) {
            return v == required; // 在所有节点均被访问的前提下，判断最后的结果是否为所需要的结果。
        }

        // 访问所有的邻接顶点
        for (int i = 0; i < nums.length; i++) {
            if (signs[i] == 0) {
                signs[i] = 1;
                if (dfs(nums, signs, v + nums[i], required) // 加法
                        || dfs(nums, signs, v - nums[i], required) // 减法
                        || dfs(nums, signs, v * nums[i], required) // 乘法
                        || nums[i] != 0 && v % nums[i] == 0 && dfs(nums, signs, v / nums[i], required)/* 除法 */) {
                    return true;// 如果可以通过四则运算得到需要的结果，则返回true。
                }
                signs[i] = 0; // 如果不能通过四则运算得到，则进行回溯。
            }
        }

        return false;//当所有情况均得不到需要的结果，返回false。
    }
}