Clean Java Solution, BFS + Bitmask + Memo
Ideas\n- This question is very similar to 877. Stone Game, of course without the math tricks. \n- n = positions.length, n is the # of pawns. We can use an int[n
## Ideas\n- This question is very similar to [877. Stone Game](https://leetcode.com/problems/stone-game/description/), of course without the math tricks. \n- `n = positions.length`, n is the # of pawns. We can use an int[n][50][50] array to find the steps starting from pawns to reach any positions of the board. Because pawns positions are fixed and knight could be at any positions of the board. We don\'t need an int[50][50][50][50] array to find all possible movement pairs.\n- For the memo, I use a HashMap<"x,y,bitmask", Integer> to record the maximum number of moves (a.k.a. final result) of a state, because a pair of <x,y,bitmask> locates a answer. Ideally we can use an int[50][50][1<<n] array, however, I got `Memory Limit Exceeds` error when I tried so, it is because the memo is actually very sparse and not being used sufficient.\n\nTime complexity: O(50 * 50 * 2^n).\n\n**Please upvote!**\n\n```java []\nclass Solution {\n    int[][][] graph;\n    Map<String, Integer> memo = new HashMap<>();\n    int[][] dirs = new int[][]{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, -1}, {-2, 1}};\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n         int n = positions.length;\n         graph = new int[n][50][50];\n         for(int i=0; i<n; i++){\n            graph[i] = bfs(positions[i][0], positions[i][1]);\n         }\n        return process(kx, ky, (1<<n)-1, positions, true);\n    }\n\n    int process(int x, int y, int mask, int[][] positions, boolean isMax){\n        int n = positions.length;\n        String key = x+","+y+","+mask;\n        if(memo.containsKey(key)) return memo.get(key);\n        if(mask==0) return 0;\n\n        int local = isMax? 0 : Integer.MAX_VALUE;\n        for(int i=0; i<n; i++){\n            if(((1<<i) & mask) ==0) continue;\n            if(isMax) local = Math.max(local, graph[i][x][y] + process(positions[i][0], positions[i][1], mask & (~(1<<i)), positions, !isMax));\n            if(!isMax) local = Math.min(local, graph[i][x][y] + process(positions[i][0], positions[i][1], mask & (~(1<<i)), positions, !isMax));\n        }\n        memo.put(key, local);\n        return local;\n    }\n\n    int[][] bfs(int i, int j){\n        boolean[][] visited = new boolean[50][50];\n        visited[i][j] = true;\n        int[][] g = new int[50][50];\n        int level = 0;\n        Queue<int[]> q = new LinkedList<>();\n        q.offer(new int[]{i, j});\n\n        while(!q.isEmpty()){\n            int size = q.size();\n            while(size-->0){\n                int[] cur = q.poll();\n                g[cur[0]][cur[1]] = level;\n                for(int[] dir: dirs){\n                    int ii = cur[0] + dir[0];\n                    int jj = cur[1] + dir[1];\n                    if(0<=ii && ii<50 && 0<=jj && jj<50 && !visited[ii][jj]){\n                        visited[ii][jj] = true;\n                        q.offer(new int[]{ii, jj});\n                    }\n                }\n            }\n            level++;\n        }\n        return g;\n    }\n}\n```
['Dynamic Programming', 'Bit Manipulation', 'Breadth-First Search', 'Memoization', 'Bitmask', 'Java']