力扣1197 进击的骑士 双端BFS

https://leetcode-cn.com/problems/minimum-knight-moves/

class Solution {
    private int mov[][] = {{-2,1},{2,1},{2,-1},{-2,-1},
                            {1,-2},{1,2},{-1,2},{-1,-2}};

    public int minKnightMoves(int x, int y) {
        Queue<int[]> queue0 = new LinkedList<int[]>();
        Queue<int[]> queue1 = new LinkedList<int[]>();
        HashMap<Integer, Integer> map0 = new HashMap<>();    //从起点出发
        HashMap<Integer, Integer> map1 = new HashMap<>();    //从终点出发

        queue0.add(new int[] {0,0});
        queue1.add(new int[] {x,y});
        map0.put(0, 0);
        map1.put(x * 1000 + y, 0);     //x*1000+y自己定义的位置hashcode

        while (map0.size() > 0 || map1.size() > 0) {
            int siz = queue0.size();

            while (siz-- > 0) {
                int cur[] = queue0.poll();
                int curHash = cur[0] * 1000 + cur[1];
                int curStep = map0.get(curHash);

                if (map1.containsKey(curHash)) {
                    return map0.get(curHash) + map1.get(curHash);
                }

                for (int i = 0; i < 8; ++i) {
                    int nx = cur[0] + mov[i][0], ny = cur[1] + mov[i][1];
                    int nHash = nx  * 1000 + ny;

                    if (map0.containsKey(nHash)) {
                        continue;
                    }

                    queue0.add(new int[]{nx, ny});
                    map0.put(nHash, curStep + 1);
                }
            }


            siz = queue1.size();
            while (siz-- > 0) {
                int cur[] = queue1.poll();
                int curHash = cur[0] * 1000 + cur[1];
                int curStep = map1.get(curHash);

                if (map0.containsKey(curHash)) {
                    return map0.get(curHash) + map1.get(curHash);
                }

                for (int i = 0; i < 8; ++i) {
                    int nx = cur[0] + mov[i][0], ny = cur[1] + mov[i][1];
                    int nHash = nx  * 1000 + ny;

                    if (map1.containsKey(nHash)) {
                        continue;
                    }

                    queue1.add(new int[]{nx, ny});
                    map1.put(nHash, curStep + 1);
                }
            }
        }

        return -1;
    }
}