1197. Minimum Knight Moves

 一刷

Version #1 BFS

TLE if we use HashMap to implement the visited grids

We should use a boolean array instead

Given the coordinate of the target as $(x, y)$, the number of cells covered by the circle that is centered at point $(0, 0)$ and reaches the target point is roughly $\big(\max(|x|, |y|)\big) ^ 2$

Time O(max(|x|, |y|)^2)

Space O(max(|x|, |y|)^2)

Runtime: 279 ms, faster than 60.99% of Java online submissions for Minimum Knight Moves.

Memory Usage: 91.8 MB, less than 54.57% of Java online submissions for Minimum Knight Moves.

class Solution {

    private int[] dx = new int[]{2, 1, -1, -2, -2, -1, 1, 2};

    private int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

    public int minKnightMoves(int x, int y) {

        if (x == 0 && y == 0) {

            return 0;

        }

        Queue<int[]> que = new ArrayDeque<>();

        boolean[][] visited = new boolean[601][601];

        que.offer(new int[]{0, 0});

        visited[300][300] = true;

        int step = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            step++;

            while (size-- > 0) {

                int[] curr = que.poll();

                // y = curr[0], x = curr[1]

                for (int i = 0; i < 8; i++) {

                    int ny = curr[0] + dy[i];

                    int nx = curr[1] + dx[i];

                    if (nx == x && ny == y) {

                        return step;

                    }

                    if (visited[ny + 300][nx + 300]) {

                        continue;

                    }

                    que.offer(new int[]{ny, nx});

                    visited[ny + 300][nx + 300] = true;

                }

            }

        }

        return -1;

    }

}

Version #2 Bidirectional BFS

这里只是记录这种bidirectional的思路

实际写的时候visited array的boundary和offsite都非常tricky, 写错了好几次

如果不用visited array而用hash成string的方法就会TLE

所以问题很多

Time 和 Space complexity都和上面是一样的

Runtime: 207 ms, faster than 68.90% of Java online submissions for Minimum Knight Moves.

Memory Usage: 74.4 MB, less than 56.56% of Java online submissions for Minimum Knight Moves.

class Solution {

    private int[] dx = new int[]{2, 1, -1, -2, -2, -1, 1, 2};

    private int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

    

    private String hash(int[] grid) {

        return grid[0] + "," + grid[1];

    }

    

    private int offsite = 600;

    public int minKnightMoves(int x, int y) {

        if (x == 0 && y == 0) {

            return 0;

        }

        // Bidirectional BFS

        // Search from both start point and the end point

        int bound = 1201;

        int[][] sourceVisited = new int[bound][bound];

        int[][] targetVisited = new int[bound][bound];

        for (int i = 0; i < bound; i++) {

            for (int j = 0; j < bound; j++) {

                sourceVisited[i][j] = -1;

                targetVisited[i][j] = -1;

            }

        }

        

        Queue<int[]> sourceQue = new ArrayDeque<>();

        sourceVisited[offsite][offsite] = 0;

        sourceQue.offer(new int[]{0, 0});

        

        Queue<int[]> targetQue = new ArrayDeque<>();

        targetVisited[x + offsite][y + offsite] = 0;

        targetQue.offer(new int[]{x, y});

        // while (!sourceQue.isEmpty() && !targetQue.isEmpty())

        // The queue will never be empty since the board is infinite, so we can just use while "true"

        while (true) {

            int dist = bfs(sourceQue, sourceVisited, targetVisited);

            if (dist > 0) {

                return dist;

            }      

            dist = bfs(targetQue, targetVisited, sourceVisited);

            if (dist > 0) {

                return dist;

            }

        }

    }

    private int bfs(Queue<int[]> que, int[][] selfVisited, int[][] otherVisited) {

        int[] curr = que.poll();

        

        // dist to the next point

        int dist = selfVisited[curr[0] + offsite][curr[1] + offsite] + 1;

        // System.out.printf("(%d,%d) -> %d", curr[0], curr[1], dist);

        for (int i = 0; i < 8; i++) {

            int nx = curr[0] + dx[i];

            int ny = curr[1] + dy[i];

            

            if (otherVisited[nx + offsite][ny + offsite] != -1) {

                return dist + otherVisited[nx + offsite][ny + offsite];

            }

            if (selfVisited[nx + offsite][ny + offsite] != -1) {

                continue;

            }

            selfVisited[nx + offsite][ny + offsite] = dist;

            que.offer(new int[]{nx, ny});

        }

        return -1;

    }

}