每日算法 — 使用java实现跳房子：BFS最短路径与动态规划最优跳跃序列

引言

跳房子（Hopscotch）是起源于古罗马的经典儿童户外游戏，玩家在画有连续方格的场地上，通过单脚跳跃或双脚并跳的方式按数字顺序前进。传统玩法要求玩家投掷石子到指定格子后，绕过该格完成剩余路径。本文将这一经典游戏抽象为图论与动态规划问题，用Java实现一个智能跳房子路径规划系统，核心讲解BFS（广度优先搜索）计算最短可达路径，以及动态规划求解在体力限制下的最优跳跃序列。

游戏规则与数学建模

经典规则抽象

假设有一条包含N个格子的直线场地，编号从1到N。玩家从起点（0号位置）出发，每次可以选择：

• 单脚跳：向前跳1格或2格，消耗体力1单位
• 双脚并跳：向前跳3格，消耗体力2单位
• 长跳：向前跳4格，消耗体力3单位

某些格子被标记为”障碍格”，玩家不能落在上面。当玩家投掷石子到格子K后，格子K变为”禁跳格”，必须跳过。目标是到达终点（N+1号位置），且总消耗体力最少。

图论建模

将每个格子视为图中的一个节点，从节点i可以到达的节点集合由跳跃规则决定：

• 从格子i，可达 {i+1, i+2, i+3, i+4} 中的非障碍、非禁跳格子
• 边权为对应的体力消耗：1, 1, 2, 3

这是一个典型的带权有向图最短路径问题。但由于图的边具有规律结构（只向前连接），我们可以用动态规划而非Dijkstra算法来高效求解。

动态规划状态设计

定义 dp[i] 为到达格子i所需的最小体力消耗。状态转移方程：

dp[i] = min(
    dp[i-1] + 1,  // 从i-1单脚跳1格
    dp[i-2] + 1,  // 从i-2单脚跳2格
    dp[i-3] + 2,  // 从i-3双脚并跳3格
    dp[i-4] + 3   // 从i-4长跳4格
)

其中，如果某个前驱格子是障碍或禁跳，则对应转移不合法。

初始条件：dp[0] = 0（起点体力消耗为0）。

BFS计算可达性

在求解最优路径之前，我们需要先判断终点是否可达。由于边权不均匀（1,1,2,3），标准的无权图BFS需要适配。这里我们采用0-1 BFS思想，使用双端队列处理不同权重的边。

0-1 BFS可达性检测

/**
 * 0-1 BFS判断终点是否可达
 * 使用双端队列，体力消耗为1的边放队首，消耗为2或3的边放队尾
 */
public boolean isReachable(int n, boolean[] blocked, int forbidden) {
    boolean[] visited = new boolean[n + 2];
    Deque<int[]> deque = new ArrayDeque<>(); // [position, cost]
    deque.offerFirst(new int[]{0, 0});
    visited[0] = true;

    while (!deque.isEmpty()) {
        int[] curr = deque.pollFirst();
        int pos = curr[0];

        if (pos == n + 1) return true; // 到达终点

        // 四种跳跃方式
        int[][] moves = {{1, 1}, {2, 1}, {3, 2}, {4, 3}};
        for (int[] move : moves) {
            int next = pos + move[0];
            int cost = move[1];

            if (next > n + 1) continue;
            if (next == forbidden) continue; // 禁跳格
            if (next <= n && blocked[next]) continue; // 障碍格
            if (visited[next]) continue;

            visited[next] = true;
            if (cost == 1) {
                deque.offerFirst(new int[]{next, cost});
            } else {
                deque.offerLast(new int[]{next, cost});
            }
        }
    }
    return false;
}

时间复杂度：O(N)，每个节点最多入队一次。
空间复杂度：O(N)。

动态规划求解最优跳跃序列

核心算法实现

import java.util.*;

public class HopscotchSolver {

    // 跳跃规则：{步数, 体力消耗}
    private static final int[][] JUMP_RULES = {{1, 1}, {2, 1}, {3, 2}, {4, 3}};

    /**
     * 求解最小体力消耗及最优跳跃序列
     * @param n 场地格子总数
     * @param blocked 障碍格标记数组，blocked[i]=true表示格子i是障碍
     * @param forbidden 禁跳格编号（石子投掷位置）
     * @return Result对象，包含最小体力、路径数组和跳跃序列
     */
    public Result solve(int n, boolean[] blocked, int forbidden) {
        int target = n + 1; // 终点位置
        int INF = Integer.MAX_VALUE / 2;
        int[] dp = new int[target + 1];
        int[] prev = new int[target + 1]; // 记录前驱节点
        int[] jumpType = new int[target + 1]; // 记录跳跃类型

        Arrays.fill(dp, INF);
        Arrays.fill(prev, -1);
        dp[0] = 0;

        for (int i = 1; i <= target; i++) {
            // 障碍格和禁跳格不可达
            if (i <= n && blocked[i]) continue;
            if (i == forbidden) continue;

            for (int[] rule : JUMP_RULES) {
                int step = rule[0];
                int cost = rule[1];
                int from = i - step;

                if (from < 0) continue;
                if (dp[from] == INF) continue; // 前驱不可达

                if (dp[from] + cost < dp[i]) {
                    dp[i] = dp[from] + cost;
                    prev[i] = from;
                    jumpType[i] = step;
                }
            }
        }

        // 回溯构造路径
        List<Integer> path = new ArrayList<>();
        List<Integer> jumps = new ArrayList<>();
        if (dp[target] != INF) {
            int curr = target;
            while (curr != -1) {
                path.add(curr);
                if (curr != 0) {
                    jumps.add(jumpType[curr]);
                }
                curr = prev[curr];
            }
            Collections.reverse(path);
            Collections.reverse(jumps);
        }

        return new Result(dp[target] == INF ? -1 : dp[target], path, jumps);
    }

    /**
     * 打印跳跃序列的可视化表示
     */
    public void printPathVisualization(int n, Result result, int forbidden) {
        if (result.minEnergy == -1) {
            System.out.println("无可达路径！");
            return;
        }

        System.out.println("最优路径（最小体力: " + result.minEnergy + "）:");
        boolean[] onPath = new boolean[n + 2];
        for (int pos : result.path) {
            if (pos <= n + 1) onPath[pos] = true;
        }

        for (int i = 0; i <= n + 1; i++) {
            if (i == forbidden) {
                System.out.print("[X] "); // 禁跳格
            } else if (onPath[i]) {
                System.out.print("[" + i + "] "); // 路径上的格子
            } else {
                System.out.print(" _  "); // 普通格子
            }
        }
        System.out.println();

        System.out.print("跳跃序列: ");
        for (int j : result.jumps) {
            String type = j == 1 ? "单脚跳1格" : j == 2 ? "单脚跳2格" : 
                         j == 3 ? "双脚跳3格" : "长跳4格";
            System.out.print(type + " -> ");
        }
        System.out.println("到达终点");
    }

    static class Result {
        int minEnergy;
        List<Integer> path;
        List<Integer> jumps;

        Result(int minEnergy, List<Integer> path, List<Integer> jumps) {
            this.minEnergy = minEnergy;
            this.path = path;
            this.jumps = jumps;
        }
    }

    public static void main(String[] args) {
        HopscotchSolver solver = new HopscotchSolver();

        // 测试用例1：无障碍
        int n1 = 10;
        boolean[] blocked1 = new boolean[n1 + 1];
        Result r1 = solver.solve(n1, blocked1, -1);
        solver.printPathVisualization(n1, r1, -1);

        // 测试用例2：有障碍和禁跳格
        int n2 = 15;
        boolean[] blocked2 = new boolean[n2 + 1];
        blocked2[5] = true;
        blocked2[8] = true;
        blocked2[12] = true;
        Result r2 = solver.solve(n2, blocked2, 7);
        solver.printPathVisualization(n2, r2, 7);

        // 测试用例3：不可达情况
        int n3 = 5;
        boolean[] blocked3 = new boolean[n3 + 1];
        blocked3[1] = true;
        blocked3[2] = true;
        blocked3[3] = true;
        blocked3[4] = true;
        Result r3 = solver.solve(n3, blocked3, -1);
        solver.printPathVisualization(n3, r3, -1);
    }
}

复杂度分析

由于K是常数4，实际时间复杂度为O(N)，对于N ≤ 10^5 的场景可以毫秒级响应。

扩展：多石子禁跳与状态压缩

当游戏允许多次投掷石子，产生多个禁跳格时，问题变为多约束最短路径。若禁跳格数量M较小（M ≤ 20），可以用状态压缩动态规划：

/**
 * 多禁跳格状态压缩DP
 * dp[i][mask] 表示到达格子i，且已激活禁跳格状态为mask时的最小体力
 */
public int solveMultiForbidden(int n, boolean[] blocked, int[] forbiddenList) {
    int m = forbiddenList.length;
    int target = n + 1;
    int INF = Integer.MAX_VALUE / 2;
    int[][] dp = new int[target + 1][1 << m];

    for (int[] row : dp) Arrays.fill(row, INF);
    dp[0][0] = 0;

    for (int i = 1; i <= target; i++) {
        if (i <= n && blocked[i]) continue;

        for (int mask = 0; mask < (1 << m); mask++) {
            // 检查当前格子是否是某个禁跳格
            boolean isForbidden = false;
            for (int j = 0; j < m; j++) {
                if (forbiddenList[j] == i && (mask & (1 << j)) == 0) {
                    isForbidden = true; // 该禁跳格尚未被"跳过"
                    break;
                }
            }
            if (isForbidden) continue;

            // 状态转移（更新mask逻辑省略，视具体规则而定）
            // ...
        }
    }
    // 返回所有mask状态下的最小值
    return Arrays.stream(dp[target]).min().orElse(-1);
}

总结

本文将跳房子游戏抽象为带约束的最短路径问题，通过BFS进行可达性预检查，再用动态规划在O(N)时间内求解最优跳跃序列。核心技巧包括：

1. 0-1 BFS：利用双端队列优化带权图的可达性检测
2. 前驱数组回溯：在DP过程中同步记录路径信息，实现结果还原
3. 多约束扩展：通过状态压缩处理多个禁跳格的复杂场景

读者可以在此基础上扩展：加入风向随机扰动（概率DP）、支持二维平面跳房子（网格BFS+DP）、或设计多玩家竞争的最优策略（博弈论）。