DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        var moveDp = new HashMap<Integer,Integer>();\n        var dp = new HashMap<Integer,Integer>();\n        int res = 0;\n        for(int i = 0; i < positions.length; i++) {\n            int moves = getMoves(kx, ky, positions[i][0], positions[i][1], moveDp);\n            int state = (i << 15) + (1 << i);\n            int k = helper(positions, state, dp, moveDp, false);\n            res = Math.max(res, moves + k);\n        }\n        return res;\n    }\n\n    int helper(int[][] positions, int state, Map<Integer,Integer> dp, Map<Integer,Integer> moveDp, boolean alice) {\n        if(dp.containsKey(state)) return dp.get(state);\n        int pi = state >> 15;\n        int res = alice ? 0 : Integer.MAX_VALUE;\n        for(int i = 0; i < positions.length; i++) {\n            if((state & (1 << i)) > 0) continue;\n            int moves = getMoves(positions[pi][0], positions[pi][1], positions[i][0], positions[i][1], moveDp);\n            int state2 = (state & ((1 << 15) - 1)) + (1 << i) + (i << 15);\n            int k = helper(positions, state2, dp, moveDp, !alice);\n            res = alice ? Math.max(res, moves + k) : Math.min(res, moves + k);\n        }\n        if(res == Integer.MAX_VALUE) {\n            res = 0;\n        }\n        dp.put(state, res);\n        return res;\n    }\n\n    int getMoves(int kx, int ky, int x, int y, Map<Integer,Integer> dp) {\n        int key = kx * 50 + ky;\n        key = key * 2500 + x * 50 + y;\n        if(dp.containsKey(key)) return dp.get(key);\n        \n        var que = new LinkedList<int[]>();\n        que.add(new int[]{kx, ky});\n        boolean[][] visited = new boolean[50][50];\n        visited[kx][ky] = true;\n        for(int moves = 0;; moves++) {\n            for(int s = que.size(); s > 0; s--) {\n                var head = que.remove();\n                int hx = head[0], hy = head[1];\n                if(hx == x && hy == y) {\n                    dp.put(key, moves);\n                    return moves;\n                }\n\n                for(int[] q: new int[][]{{1,1}, {1,-1}, {-1,1}, {-1,-1}}) {\n                    for(int[] d : new int[][]{{1,2}, {2,1}}) {\n                        int x2 = hx + q[0] * d[0];\n                        int y2 = hy + q[1] * d[1];\n                        if(x2 < 0 || x2 > 49 || y2 < 0 || y2 > 49) continue;\n                        if(visited[x2][y2]) continue;\n                        visited[x2][y2] = true;\n                        que.add(new int[]{x2, y2});\n                    }\n                }\n            }\n            \n        }\n    }\n}\n```
['Java']