题解 | 象棋马走步问题先用bfs找最短距离，再用dfs找路径

import java.util.*;

public class Main {
    private static final int[][] directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
    private static Set<Integer> set = new HashSet<>();
    private static List<List<Integer>> ans = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) set.add(sc.nextInt());
        int start = sc.nextInt(), end = sc.nextInt();
        sc.close();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        int[][] minDist = new int[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                minDist[i][j] = Integer.MAX_VALUE;
            }
        }
        int step = 0;
        minDist[start / 8][start % 8] = 0;
        Label:
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int cur = queue.poll();
                minDist[cur / 8][cur % 8] = step;
                if (cur == end) break Label;
                for (int[] dir : directions) {
                    int nx = cur / 8 + dir[0], ny = cur % 8 + dir[1], next = nx * 8 + ny;
                    if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8 || set.contains(next) || minDist[nx][ny] <= step + 1)
                        continue;
                    queue.offer(next);
                }
            }
            step++;
        }
        if (minDist[end / 8][end % 8] == Integer.MAX_VALUE) System.out.println("UNREACHED");
        else {
            List<Integer> path = new LinkedList<>();
            path.add(end);
            dfs(end, start, minDist, path);
            ans.sort((a, b) -> {
                for (int i = a.size() - 1; i >= 0; i--) {
                    if (a.get(i) != b.get(i)) return a.get(i) - b.get(i);
                }
                return 0;
            });
            for (final List<Integer> res : ans) {
                for (int i = res.size() - 1; i >= 0; i--) System.out.print(res.get(i) + " ");
                System.out.println();
            }
        }
    }

    private static void dfs(int cur, int end, int[][] minDist, List<Integer> path) {
        if (cur == end) {
            ans.add(new LinkedList<>(path));
            return;
        }
        for (int[] dir : directions) {
            int nx = cur / 8 + dir[0], ny = cur % 8 + dir[1];
            int next = nx * 8 + ny;
            if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8 || set.contains(next) || minDist[nx][ny] != minDist[cur / 8][cur % 8] - 1)
                continue;
            path.add(next);
            dfs(next, end, minDist, path);
            path.remove(path.size() - 1);
        }
    }
}