# 1197. Minimum Knight Moves
###### tags: `Leetcode` `FaceBook` `Medium` `BFS`
Link: https://leetcode.com/problems/minimum-knight-moves/
## 思路
如果直接用bfs，不用visited会TLE
因为给的边界是无限大的，所以不能建visited array去记录，这里改用set
set里面可以用pair存，也可以用string的形式存（但是花的时间会更久）
但加了visited之后还是会TLE
因此利用对称的特性，做一些剪枝，我们把xy全都变成正的，这样我们就可以只在第一象限找答案，并且在做bfs的时候，对加进queue的点加限制条件
但**限制条件不能是```newi>=0 && newj>=0```**，这样的话从[0,0]到[1,1]的路径就会错，因为一定要先到[-1,2]，再到[1,1]才行
## Code

class Solution {
    int[][] directions = new int[][]{{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
    public int minKnightMoves(int x, int y) {
        x = Math.abs(x);
        y = Math.abs(y);
        int depth = 0;
        Queue<int[]> q = new LinkedList<>();
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        visited.add(new Pair<>(0,0));
        q.add(new int[]{0,0});
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                int[] curr = q.poll();
                if(curr[0]==x && curr[1]==y){
                    return depth;
                }
                for(int j = 0;j < directions.length;j++){
                    int newi = curr[0]+directions[j][0];
                    int newj = curr[1]+directions[j][1];
                    if(!visited.contains(new Pair<>(newi, newj)) && newi>=-1 && newj>=-1){
                        q.add(new int[]{newi, newj});
                        visited.add(new Pair<>(newi, newj));
                    }
                }   
            }
            depth++;
        }
        return 0;
    }
}