Beats 100% time and 100% space complexity. Recursion and Memo
Intuition\nwe are precomputing the shortest distances from one knight to other using bfs and then by using recursion,memo,gametheory and bit masking we are good
# Intuition\nwe are precomputing the shortest distances from one knight to other using bfs and then by using recursion,memo,gametheory and bit masking we are good to go...\n\n# Approach\n1-create a new arraylist and add starting position of knight and all position of pawns in it\n2-Iterate an index over position arraylist which we created just now and for every index calculate shortest path to reach pawn. if index=0 then we are calculating shortest distance from (0,2) to (1,1) and so on\n3-once we complete an iteration of an index then we store the min distance in our mindistance array which we will create before bfs pass it in bfs.\n4-after completing iteration of bfs we will store shortest distance in our mindistance array which we will get from out t[][](temp) array.\n5-we will create a mask of size of array for eg: if there are 3 pawns then mask will be of size 3 \n6-we will use xor & and to know if any pawn is destroyed or not\n7-while applying recursion alice will try to get max moves and bob will take min moves so we have to keep an eye on it\n8-we will then apply memo to our recursion and we can skip the alice&bob\'s one so we can take 2d dp array because it will work without them\n\n# Complexity\n- Time complexity:\nO(N\u221750\u221750)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    \tstatic int[][]directions= {{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        int n=positions.length;\n\t\tList<int[]> pos=new ArrayList<int[]>();\n\t\tpos.add(new int[] {kx,ky});\n\t\tfor(int []p:positions) {\n\t\t\tpos.add(new int[] {p[0],p[1]});\n\t\t}\n\t\tint[][]mindist=new int[n+1][n+1];\n\t\tfor(int index=0;index<pos.size();index++) {\n\t\t\tint x=pos.get(index)[0];\n\t\t\tint y=pos.get(index)[1];\n\t\t\tbfs(x,y,index,pos,mindist);\n\t\t}\n\t\tint[][]dp=new int[51][1<<15];\n\t\tfor(int[]r:dp)Arrays.fill(r, -1);\n\t\treturn solvex(mindist,0,(1<<n)-1,pos.size(),true,dp);\n    }\n\tprivate static int solvex(int[][] mindist, int idx, int mask, int n, boolean alice,int[][]dp) {\n\t\tif(mask==0)return 0;\n\t\tif(dp[idx][mask]!=-1)return dp[idx][mask];\n\t\tint res=(alice)?-1:Integer.MAX_VALUE;\n\t\tfor(int i=1;i<n;i++) {\n\t\t\tif ((mask & (1 << (i - 1))) != 0)  {\n\t\t\t\tint moves=mindist[idx][i];\n\t\t\t\tif(alice) {\n\t\t\t\t\tres=Math.max(res, moves+solvex(mindist, i, (mask^(1<<(i-1))), n, !alice,dp));\n\t\t\t\t}\n\t\t\t\telse\n\t\t\t\t\tres=Math.min(res, moves+solvex(mindist, i, (mask^(1<<(i-1))), n, !alice,dp));\n\t\t\t}\n\t\t}\n\t\treturn dp[idx][mask]=res;\n\t}\n\tprivate static void bfs(int x, int y, int index, List<int[]> pos, int[][] mindist) {\n\t\tQueue<int[]>q=new LinkedList<int[]>();\n\t\tq.add(new int[] {x,y});\n\t\tint[][]t=new int[51][51];\n\t\tfor(int []r:t)Arrays.fill(r, -1);\n\t\tt[x][y]=0;\n\t\twhile(!q.isEmpty()) {\n\t\t\tint []temp=q.poll();\n\t\t\tint currx=temp[0];\n\t\t\tint curry=temp[1];\n\t\t\tfor(int[]dir:directions) {\n\t\t\t\tint newx=currx+dir[0];\n\t\t\t\tint newy=curry+dir[1];\n\t\t\t\tif(newx>=0 && newx<50 && newy>=0 && newy<50 && t[newx][newy]==-1) {\n\t\t\t\t\tt[newx][newy]=1+t[currx][curry];\n\t\t\t\t\tq.add(new int[] {newx,newy});\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tfor(int i=0;i<pos.size();i++) {\n\t\t\tint x_=pos.get(i)[0];\n\t\t\tint y_=pos.get(i)[1];\n\t\t\tmindist[index][i]=t[x_][y_];\n\t\t}\n\t\t\n    }\n}\n```
['Java']