JAVA || Beats 100% || BFS + DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nwe have atmax 15 pawn p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe have atmax 15 pawn positions to deal with so we would find distance between any pair of positions then the problem reduces to a dp problem where we have to visit all positions exactly once such that its cost is maximum.\n\nNow to find distance between any two pawn position, firstly make a graph then using modified bfs, store these distances in a 2D array.\n\nNOTE - we have to map each cell with a number so that (i,j) -> num for easy reference to any cell.\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\n    static void bfs(List<Integer>  graph[], int S, List<Integer> dist)\n    {\n        Queue<Integer> q = new LinkedList<>();\n        dist.set(S, 0);\n        q.add(S);\n\n        while (!q.isEmpty()) {\n            int node = q.poll();\n\n            for (int neighbor : graph[node]) {\n                if (dist.get(neighbor)\n                    == Integer.MAX_VALUE) {\n                    dist.set(neighbor, dist.get(node) + 1);\n                    q.add(neighbor);\n                }\n            }\n        }\n    }\n\n    static void\n    printShortestDistance(List<Integer>  graph[], int S, int V,int a[][],int distance[][],int i,int len,int positions[][])\n    {\n\n        // dist[] array stores the distance of nodes from S\n        List<Integer> dist = new ArrayList<>(\n            Collections.nCopies(V, Integer.MAX_VALUE));\n\n        // Function call to find the distance of all nodes\n        // and their parent nodes\n        bfs(graph, S, dist);\n        \n        for(int j=0;j<len;j++){\n            distance[i][j]=distance[j][i]=dist.get(a[positions[j][0]][positions[j][1]]);\n        }\n\n\n    }\n\n    static void\n    duplicateShortestDistance(List<Integer>  graph[], int S, int V,int a[][],int distance[],int len,int positions[][])\n    {\n\n        // dist[] array stores the distance of nodes from S\n        List<Integer> dist = new ArrayList<>(\n            Collections.nCopies(V, Integer.MAX_VALUE));\n\n        // Function call to find the distance of all nodes\n        // and their parent nodes\n        bfs(graph, S, dist);\n        \n        for(int j=0;j<len;j++){\n            distance[j]=dist.get(a[positions[j][0]][positions[j][1]]);\n        }\n\n\n    }\n\n\n\n\n\n// \n\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        int a[][]=new int[50][50];\n        int n=0;\n        for(int i=0;i<50;i++){\n            for(int j=0;j<50;j++){\n                a[i][j]=n;\n                n++;\n            }\n        }\n        ArrayList<Integer>graph[]=new ArrayList[n];\n        for(int i=0;i<n;i++){\n            graph[i]=new ArrayList<>();\n        }\n        for(int i=0;i<50;i++){\n            for(int j=0;j<50;j++){\n                if(i+2<50 && j+1<50){\n                graph[a[i][j]].add(a[i+2][j+1]);\n                }\n                if(i+2<50 && j-1>=0){\n                graph[a[i][j]].add(a[i+2][j-1]);\n                }\n                if(i-2>=0 && j+1<50){\n                graph[a[i][j]].add(a[i-2][j+1]);\n                }\n                if(i-2>=0 && j-1>=0){\n                graph[a[i][j]].add(a[i-2][j-1]);\n                }\n                // \n                if(j+2<50 && i+1<50){\n                graph[a[i][j]].add(a[i+1][j+2]);\n                }\n                if(j+2<50 && i-1>=0){\n                graph[a[i][j]].add(a[i-1][j+2]);\n                }\n                if(j-2>=0 && i+1<50){\n                graph[a[i][j]].add(a[i+1][j-2]);\n                }\n                if(j-2>=0 && i-1>=0){\n                graph[a[i][j]].add(a[i-1][j-2]);\n                }\n            }\n        }\n        int len=positions.length;\n        int dist[][]=new int[len][len];\n        for(int i=0;i<len;i++){\n            printShortestDistance(graph, a[positions[i][0]][positions[i][1]],n,a,dist,i,len,positions);\n        }\n\n        // for(int i=0;i<len;i++){\n        //     for(int j=0;j<len;j++){\n        //         System.out.print(dist[i][j]+" ");\n        //     }\n        //     System.out.println();\n        // }\n\n       HashMap<Long,Integer> dp[][]=new HashMap[len][2];\n       for(int i=0;i<len;i++){\n        for(int j=0;j<2;j++){\n            dp[i][j]=new HashMap<>();\n        }\n       }\n\n       int ans=0;\n       int array[]=new int[len];\n       duplicateShortestDistance(graph, a[kx][ky],n,a,array,len,positions);\n       for(int i=0;i<len;i++){\n        ans=Math.max(ans,array[i]+fun(dist,len,(long)1<<i,1,dp,i));\n       }\n       return ans;\n\n        \n\n\n\n\n\n    }\n\n    public static int fun(int dist[][],int n,long mask, int turn,HashMap<Long,Integer> dp[][],int i){//i is starting position\n\n        if(dp[i][turn].containsKey(mask)){\n            return dp[i][turn].get(mask);\n        }\n        int op=Integer.MIN_VALUE;\n        if(turn!=0){\n            op=Integer.MAX_VALUE;\n        }\n        int chk=0;\n        for(int j=0;j<n;j++){\n\n            if((mask&((long)1<<j))==0){\n                int x=dist[i][j]+fun(dist,n,(mask|((long)1<<j)),turn^1,dp,j);\n                \n        // System.out.println(i+" "+j+" "+x+" "+dist[i][j]);\n                if(turn==0){\n                    op=Math.max(op,x);\n                }else{\n                    op=Math.min(op,x);\n                }\n                chk=1;\n            }\n        }\n        if(chk==0){\n            op=0;\n        }\n        dp[i][turn].put(mask,op);\n        return op;\n    }\n}\n```
['Java']