骑士的最短路径：从暴力递归到终极优化

MrHe··3 min read

今天咱们聊一个老朋友，国际象棋里的“马”。它的走法很特别，走“日”字。在棋盘上，从一个点 (0,0) 跳到另一个点 (x, y)，最少要跳几步？

这个问题，面试里挺常见的。它不是一个纯粹的模拟题，更像是一个图论问题，但它的解法演进过程，非常清晰地展示了我们解决算法问题时思维提升的路径。

咱们就从最愣头青的解法开始，一步步把它干到最优。

解法一：暴力递归（天真的莽夫）

拿到这个问题，我的第一反应是啥？

一个点有8个方向可以跳。那我就从 (0,0) 开始，对着8个方向，挨个“递归”地去试。哪个方向能最快跳到 (x, y)，那不就行了？

这就是最纯粹的暴力搜索，或者叫深度优先搜索（DFS）。

思路很简单：

  1. 写一个函数 process(curX, curY)，表示从 (curX, curY) 跳到目标 (x, y) 还需要多少步。

  2. Base Case: 如果 curX == x 且 curY == y，那说明已经到地方了，一步都不用走了，返回0。

  3. 递归过程: 从 (curX, curY) 遍历8个可以跳的位置 (nextX, nextY)。对每个位置，我都去递归调用 process(nextX, nextY)，然后再加上我自己这一步（+1）。

  4. 最后，把8个方向返回的结果取个最小值，就是答案。

听起来挺完美的。但是，这里有个巨大的坑。如果我的目标点是 (1,1)，我从 (0,0) 可能跳到 (2,1)，然后我又可能从 (2,1) 跳回 (0,0)。这不就死循环了？而且，棋盘是无限大的，我这一递归下去，天荒地老，栈都给你干爆了。

就算不考虑无限棋盘，这个递归也会疯狂地重复计算。比如，从 (0,0) 到 (4,4)，我可能会经过 (2,1)；另一条路线也可能经过 (2,1)。那 process(2,1) 这个子问题就会被重复算无数遍。

所以这个思路，纯属理论，代码写出来也是超时的命，我们就不贴出来丢人了。它只是我们思考的起点。

解法二：记忆化搜索（聪明的莽夫）

既然暴力递归有重复计算和死循环的问题，那就解决它。

  1. 解决重复计算：搞个缓存。我用一个 Map<String, Integer> 来存已经算过的点的结果。key 就是坐标 "x,y"，value 就是从这个点到终点的最小步数。每次递归前，先查缓存，有就直接返回，没有再算，算完存进去。

  2. 解决死循环：搞个 Set<String> 记录当前这条递归路径上已经访问过的点。递归下去之前，把当前点加进去；回溯的时候，再把它移出来。这样保证在一条路径上不会反复横跳。

这样一改，代码就能跑了，不会超时了。本质上还是DFS，但加上了缓存（Memoization），把一颗巨大的搜索树剪掉了很多重复的枝干。

但是，这真的是最好的方法吗？

DFS的特点是“一条路走到黑”。它会先深入探索某一个分支，直到找到目标或者碰壁。但它找到的第一个解，不一定是最短的。为了找到最短的，它必须把所有可能的路径都走一遍，然后比较。虽然有缓存，但搜索的“形状”是不变的。

这就像你在迷宫里找出口，DFS是见着一条路就闷头往里冲。对于“最短路径”这类问题，我们有更好的模型。

import java.util.HashMap;
import java.util.Map;

// 解法二：记忆化搜索 (DFS + Memoization)
// 注意：这个解法在某些平台仍然可能因为递归深度或搜索范围过大而超时，
// 但它体现了从暴力到优化的重要一步。
public class KnightMovesDFS {

    private Map<String, Integer> memo = new HashMap<>();

    public int minKnightMoves(int x, int y) {
        // 由于棋盘对称性，我们只考虑第一象限，可以加速
        return dfs(Math.abs(x), Math.abs(y));
    }

    private int dfs(int x, int y) {
        // Base Case
        if (x == 0 && y == 0) {
            return 0;
        }
        if (x + y == 2) { // (1,1) -> 2, (0,2) -> 2, (2,0) -> 2
            return 2;
        }

        String key = x + "," + y;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // 递归： 我们是从(x,y)往(0,0)找，这样目标唯一，更容易处理
        // 骑士可以跳8个方向，反向跳也是一样的，所以从(x,y)跳到(x-1, y-2)等价于从(x-1, y-2)跳到(x,y)
        // 我们只考虑跳向原点的方向，所以x和y都是减小的
        int res = Math.min(
            dfs(Math.abs(x - 1), Math.abs(y - 2)),
            dfs(Math.abs(x - 2), Math.abs(y - 1))
        ) + 1;

        memo.put(key, res);
        return res;
    }
}

这里的DFS代码做了个小技巧：从 (x, y) 往 (0, 0) 找，因为目标是固定的，更好处理。同时利用了对称性，只在第一象限搜索，并且只考虑让坐标减小的两个方向，这是一种强剪枝，能避免大部分死循环和无效搜索。

解法三：广度优先搜索（BFS，标准解法）

一提到“无权图的最短路径”，我的DNA就动了。这不就是BFS的专属领域吗？

把整个无限棋盘看作一个图，每个坐标点是一个节点。如果两个点可以通过一次骑士跳跃到达，它们之间就有一条边。我们要求 (0,0) 到 (x,y) 的最短路径，就是求这两个节点在图中的最短距离。

BFS的思想，就像往水里扔一块石头，波纹是一圈一圈往外扩散的。

  • 第0圈：就是起点 (0,0)。

  • 第1圈：从 (0,0) 跳一步能到的所有点。

  • 第2圈：从第1圈的点再跳一步能到的所有点。

  • ...

它是一层一层地向外探索。所以，当它第一次到达目标点 (x,y) 的时候，经过的层数，一定就是最短的步数。

BFS的标准套路：

  1. 队列(Queue)：用来存放待访问的节点。

  2. 集合(Set)：用来存放已经访问过的节点，防止走回头路和重复处理。

  3. 循环：

    • 把起点 (0,0) 和步数0放进队列。

    • 把起点 (0,0) 放进 visited 集合。

    • 当队列不空，就一直循环。

    • 每一轮循环，处理当前队列里的所有节点（也就是同一层的节点）。

    • 从队列里取出一个点，遍历它能跳到的8个新位置。

    • 如果新位置没被访问过：

      • 如果是终点，直接返回当前步数 + 1。

      • 如果不是终点，就把它加入队列和 visited 集合。

    • 处理完一层后，总步数加1。

这个方法，逻辑清晰，是这类问题的标准模板，面试写这个，稳了。

代码实现与优化

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

// 解法三：广度优先搜索 (BFS)
public class KnightMovesBFS {

    public int minKnightMoves(int x, int y) {
        // 坐标取绝对值，利用对称性，把目标点统一到第一象限
        // (1,2) 和 (-1, 2), (1, -2), (-1,-2) ... 步数都一样
        x = Math.abs(x);
        y = Math.abs(y);

        Queue<int[]> queue = new LinkedList<>();
        // 队列里存 {x, y}
        queue.offer(new int[]{0, 0});

        Set<String> visited = new HashSet<>();
        // 记录访问过的点 "x,y"
        visited.add("0,0");

        // 8个方向
        int[][] dirs = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, 
                        {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int curX = cur[0];
                int curY = cur[1];

                if (curX == x && curY == y) {
                    return steps;
                }

                // 探索8个方向
                for (int[] dir : dirs) {
                    int nextX = curX + dir[0];
                    int nextY = curY + dir[1];
                    String nextPos = nextX + "," + nextY;

                    // 剪枝优化：因为目标在第一象限，没必要往负方向探索太远
                    // 比如目标是(1,1)，我跳到(-10,-10)显然是绕远了
                    // nextX >= -1 和 nextY >= -1 是一个比较有效的经验剪枝
                    if (!visited.contains(nextPos) && nextX >= -1 && nextY >= -1) {
                        visited.add(nextPos);
                        queue.offer(new int[]{nextX, nextY});
                    }
                }
            }
            steps++;
        }
        return -1; // 理论上总能到，走不到返回-1
    }
}

这个BFS版本已经非常好了，引入了象限对称性和简单的边界剪枝，效率很高。

解法四：双向BFS（究极进化）

如果目标点 (x, y) 离 (0,0) 非常远，比如 (300, 300)，那BFS的搜索圈会变得非常大。就像一个大饼，半径越大，面积（搜索的点数）是平方级增长的。

怎么优化？

既然你从起点出发可以找到终点，那从终点出发也一定能找到起点。

双向BFS就是这个思路：

  • 一个BFS从 (0,0) 开始，叫 forwardQueue。

  • 另一个BFS从 (x,y) 开始，叫 backwardQueue。

  • 两个搜索同时进行，一圈一圈地扩大。

  • forwardQueue 每扩展一层，就去 backward 的 visited 集合里看看有没有交集。

  • backwardQueue 每扩展一层，也去 forward 的 visited 集合里看看有没有交集。

  • 一旦在某一层扩展时，发现一个点已经被另一方的BFS访问过了，那就说明两军会师了！路径找到了！

总步数就是 forward 走的步数 + backward 走的步数。

为什么快？ 假设最短路径是20步。

  • 单向BFS要搜10层，搜索半径是10，面积大概是 π * 10^2。

  • 双向BFS，两边各搜5层，半径都是5，总面积大概是 2 * π * 5^2。 100π 对比 50π，搜索空间直接砍半，甚至更多。距离越远，优势越明显。

这个实现起来稍微复杂一点，需要两个队列和两个 visited 集合，并且为了效率，每次都应该从节点数少的那一端开始扩展。但这个思想非常重要，是BFS的终极优化形态。

因为代码比较长，这里就不贴了，重点是理解这个“两头堵”的思想。

总结

回顾一下我们的心路历程：

  1. 暴力递归：最直观的想法，但会因重复计算和死循环而崩溃。

  2. 记忆化搜索：加上缓存，解决了重复计算，是暴力递归的优化版。但依然是DFS的深度探索模式，不一定最适合找最短路。

  3. BFS：最短路径问题的标准答案。逐层搜索，保证了第一次找到的就是最优解。逻辑清晰，代码稳健。

  4. 双向BFS：BFS的进阶优化。当起点和终点距离很远时，能大幅缩减搜索空间。

  • #6aqr5aor55qe5pya55t6lev5b6e