题解 | 时津风的资源收集

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;
//题目可以通过bfs或者dp解决
//用bfs的话需要考虑重复计算问题，如果每个数据都进行一次bfs将会超时
//所以可以预计算dist，将期间所有数需要操作的次数都用bfs统计一遍
//后续每个数据都可以查表解决
public class Main {
    static int[] offset = new int[] {1, -1, 10, -10, 100, -100};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { 
            int n = in.nextInt();
            in.nextLine();
            //预计算dist
            int[] dist=getDist();
            while (n > 0) {
                n--;
                int[] target = new int[4];
                for (int i = 0; i < 4; i++) {
                    target[i] = in.nextInt();
                }
                in.nextLine();
                //查表直接累加操作次数即可
                int count = 0;
                for (int i = 0; i < 4; i++) {
                    count+=dist[target[i]];
                }
                System.out.println(count);
            }
        }
    }
    //获取从10开始达到所有可能数字的操作次数
    public static int[] getDist() {
        int[] dist=new int[301];//最高数据300，为了方便使用直接给到301长度
        Arrays.fill(dist,-1);//初始值设定为-1方便检查
        Deque<int[]> que = new ArrayDeque<>();
        int count = 0;
        que.offer(new int[]{10, 0});//从10开始搜索
        que.offer(new int[]{300,1});//初始设置为上限，从300开始搜索，此次已经操作一次
        dist[10]=0;
        dist[300]=1;
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            //遍历每个偏移量
            for (int i = 0; i < offset.length; i++) {
                int nn = cur[0] + offset[i];
                //初次到达时赋值dist并入队
                if (nn >= 10 && nn <= 300 &&dist[nn]==-1) {
                    que.offer(new int[] {nn, cur[1] + 1});
                    dist[nn]=cur[1]+1;
                }
            }
        }
        // System.out.println(count);
        return dist;
    }
}