Shortest Knight Move

就是在象棋棋盘上给你两个点A，B，问 个Knight( 哥说，就是骑 那个哈)最少要几步从A跳到B。 珠从来没玩过 国际象棋，于是问Knight咋 。Turns out只要 任意朝向的L形就好。具体来说，如coordinate是(x,y) 那么在这 的 只knight可以跳到 个position中任何 个: (x-2,y-1); (x-2,y+1);(x+2,y-1);(x+2,y+1);(x-1,y+2);(x-1,y-2);(x+1,y-2);(x+1,y+2).

此题不需要建立matrix棋盘矩阵，直接使用坐标BFS即可。

* 因为是infinite matrix，所以DP、DFS不可行，用BFS做
* 1. a list of directions (int[])
* 2. a queue for BFS
* 3. a set to keep track of visited positions
* 4. an int move to keep track of current level of BFS
* 每次while loop iteration，对现在的层数的所有node进行BFS

public int shortestKnightMove(int a1, int a2, int b1, int b2) {
    int[][] dirs = new int[][]{{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
    Queue<int[]> q = new LinkedList<>();
    boolean[][] visited = new boolean[8][8];
    q.offer(new int[]{a1, a2});
    visited[a1][a2] = true;
    int dist = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] pos = q.poll();
            for (int[] d : dirs) {
                int x = pos[0] + d[0], y = pos[1] + d[1];
                if (x == b1 && y == b2)        return dist + 1;
                if (x < 0 || x >= 8 || y < 0 || y >= 8 || visited[x][y])    continue;
                visited[x][y] = true;
                q.offer(new int[]{x, y});
            }
        }
        dist++;
    }
    return -1;
}

另一种写法

    public static int shortestKnightMove(int x1, int y1, int x2, int y2) {
        int[][] directions = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
        Set<int[]> visited = new HashSet<>();
        int[] start = new int[]{x1, y1};
        visited.add(start);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        int move = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                for (int[] direction : directions) {
                    int x = pos[0] + direction[0], y = pos[1] + direction[1];
                    if (x == x2 && y == y2) return move + 1;
                    int[] newPos = new int[]{x, y};
                    if (visited.contains(newPos)) continue;
                    visited.add(newPos);
                    queue.offer(newPos);
                }
            }
            move++;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(shortestKnightMove(0,0, 3,5));
    }