1197. Minimum Knight Moves

你需要意识到无论[x, y]在哪个象限，只要他与（0，0）的距离相等，实际在哪个象限都是等价的

so 取 abs for x, y (target)

有一个细节需要注意的是虽然我们对[x, y]取了绝对值，但是并不意味着路径中不会经过

"坐标值为负 "的点。例子就是

(0, 0) -> (2, -1) -> (1, 1)

2,-1 1,2

so 需要判斷 >= -1 這個條件, or >= -2

private boolean isValid(int x, int y, Set<String> visited) {
    return x >= -2 && y >= -2 && !visited.contains(x + "," + y);
}

T: O(mn), mn is the total cell we traversed

S: O(mn)

class Solution {
    private static final int[][] DIRS = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
    public int minKnightMoves(int x, int y) {
        x = Math.abs(x);
        y = Math.abs(y);
        
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited.add(0 + "," + 0);
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int[] cur = queue.poll();
                int curX = cur[0];
                int curY = cur[1];
                
                if (curX == x && curY == y) {
                    return steps;
                }
                
                for (int[] dir : DIRS) {
                    int nextX = curX + dir[0];
                    int nextY = curY + dir[1];
                    
                    if (!isValid(nextX, nextY, visited)) {
                        continue;
                    }
                    queue.offer(new int[]{nextX, nextY});
                    visited.add(nextX + "," + nextY);
                }
            }
            steps++;
        }
        return -1;
    }
    private boolean isValid(int x, int y, Set<String> visited) {
        return x >= -2 && y >= -2 && !visited.contains(x + "," + y);
    }
}ja