第十一届蓝桥杯国赛JavaB组 试题H：画廊（题目+题解）

去年参赛还比较嫩，什么算法也不懂只能无脑算，这道题也没做出来。今年再冲一次国赛，看看去年的题，这道题应该是贪心算法，每次去找最近的点，我写的可能有些麻烦，但是运行起来还可以，用的辅助变量比较多，应该会占用不少内存
题目：
代码：

package LinkCode;


import java.text.DecimalFormat;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class L5 {
    public static void main(String[] args) {
        //Stack 存储路径
        Stack res = new Stack();
        //画的位置
        int[][] p1 = {{1, 0}, {3, 0}, {8, 0}};
        int[][] p2 = {{2, 2}, {4, 2}, {5, 2}, {6, 2}};
        //起始，结束位置
        int[] start = {0, 1};
        int[] end = {10, 1};
        //判断点是否走过
        Map<String, Boolean> flags = new HashMap<>();
        double sum = 0;
        //有几幅画就走几步
        for (int x = 0; x < p1.length + p2.length; x++) {
//            if (start[0] == 8 && start[1] == 0) {
//                break;
//            }
            Map<String, Double> map = new HashMap<>();
            double min = Double.MAX_VALUE;
            for (int i = 0; i < p1.length; i++) {
                if (flags.containsKey(p1[i][0] + "," + p1[i][1]) == false) {
                    double pows = Math.pow(Math.pow(p1[i][0] - start[0], 2) + Math.pow(p1[i][1] - start[1], 2), 0.5);
                    if (pows < min) min = pows;
                    map.put(p1[i][0] + "," + p1[i][1], pows);

                }
            }
            for (int i = 0; i < p2.length; i++) {
                if (flags.containsKey(p2[i][0] + "," + p2[i][1]) == false) {
                    double pows = Math.pow(Math.pow(p2[i][0] - start[0], 2) + Math.pow(p2[i][1] - start[1], 2), 0.5);
                    if (pows < min) min = pows;
                    map.put(p2[i][0] + "," + p2[i][1], pows);
                }
            }

            //获取第一次出现最小值的key
            Set<String> key = map.keySet();
            String[] newpos = null;
            for (String k :
                    key) {
                if (map.get(k) == min) {
                    //获取最小值的数组下标
                    newpos = k.split(",");
                    //不break会出现相同距离时选择后面的点而不选前面的点
                    break;
                }
            }
            System.out.println("min = " + min);
            start[0] = Integer.parseInt(newpos[0]);
            start[1] = Integer.parseInt(newpos[1]);
            //存储路径，记录已经走过
            res.add("(" + start[0] + "," + start[1] + ")");
            flags.put(start[0] + "," + start[1], true);
            sum += min;
        }
        //加上最后一个点到终点的距离
        sum += Math.pow(Math.pow(end[0] - start[0], 2) + Math.pow(end[1] - start[1], 2), 0.5);
        //四舍五入
        DecimalFormat df = new DecimalFormat("#.00");
        System.out.println("sum = " + df.format(sum));
        System.out.println("res = " + res);
    }
}

运行结果：

min = 1.4142135623730951
min = 2.0
min = 2.23606797749979
min = 2.0
min = 1.0
min = 1.0
min = 2.8284271247461903
sum = 14.71
res = [(1,0), (3,0), (2,2), (4,2), (5,2), (6,2), (8,0)]

自我感觉我的代码写的又臭又长，但是看着应该比较流畅，不像csdn里面大佬写的让人看都无从下眼，可能是我比较菜