赛码-接金币-java

题目描述

小赛非常喜欢玩游戏，最近喜欢上了一个接金币的游戏。在游戏中，使用帽子左右移动接金币，金币接的越多越好，但是金币掉到地上就不能再接了。为了方便问题的描述，我们把电脑屏幕分成11格，帽子每次能左右移动一格。现在给电脑屏幕如图标上坐标：

也就是说在游戏里，金币都掉落在0-10这11个位置。开始时帽子刚开始在5这个位置，因此在第一秒，帽子只能接到4,5,6这三个位置中其中一个位置上的金币。问小赛在游戏中最多可能接到多少个金币？（假设帽子可以容纳无穷多个金币）。

主要思路：
模拟法

见代码：

import java.util.*;

/**
 * 接金币
 */
public class Saima15 {
    private static int max = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int total = scan.nextInt();
        int maxTime = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        while (total > 0) {
            int pos = scan.nextInt();
            int time = scan.nextInt();
            maxTime = Math.max(maxTime, time);
            if (map.containsKey(time)) {
                map.get(time).add(pos);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(pos);
                map.put(time, list);
            }
            total--;
        }
        dfs(map, 0, 5, 1, maxTime);
        System.out.println(max);
    }

    /**
     * 不断地遍历所有的可能
     *
     * @param map
     * @param count    当前获得的金币
     * @param currPos  当前的位置
     * @param currTime 当前的时间
     * @param maxTime  最后结束的时间
     */
    private static void dfs(Map<Integer, List<Integer>> map, int count, int currPos, int currTime, int maxTime) {
        if (currTime > maxTime) {
            return;
        }
        if (currPos < 0 || currPos > 10) {
            return;
        }
        if (map.containsKey(currTime)) {
            List<Integer> data = map.get(currTime);
            if (data.contains(currPos)) {
                for (int i : data) {
                    if (i == currPos) {
                        count++;
                    }
                }
                max = Math.max(count, max);
                dfs(map, count, currPos, currTime + 1, maxTime);
                return;
            } else if (currPos - 1 >= 0 && data.contains(currPos - 1)) {
                for (int i : data) {
                    if (i == currPos - 1) {
                        count++;
                    }
                }
                max = Math.max(count, max);
                dfs(map, count, currPos - 1, currTime + 1, maxTime);
                return;
            } else if (currPos + 1 <= 10 && data.contains(currPos + 1)) {
                for (int i : data) {
                    if (i == currPos + 1) {
                        count++;
                    }
                }
                max = Math.max(count, max);
                dfs(map, count, currPos + 1, currTime + 1, maxTime);
                return;
            }

        }
        dfs(map, count, currPos,currTime + 1, maxTime);
        dfs(map, count, currPos - 1, currTime + 1, maxTime);
        dfs(map, count, currPos + 1, currTime + 1, maxTime);

    }
}