Java
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    Map<String,Integer>hmap;\n    List<String>list;\n    int[][] dist;\n    int[][] dir = {{-2,-1},{-2,1},{-1,-2},{1,-2},{2,-1},{2,1},{-1,2},{1,2}};\n    int allMask;\n    public int[][][] dp;\n\n    public int[] getNodeValue(String str){\n        String[] w = str.split("-");\n        return new int[]{Integer.valueOf(w[0]),Integer.valueOf(w[1])};\n    }\n\n    public void find(int startNode){\n        int[][] vis = new int[50][50];\n        int[] temp = getNodeValue(list.get(startNode));\n        Queue<int[]>q = new LinkedList<>();\n        q.add(new int[]{0,temp[0],temp[1]});\n        vis[temp[0]][temp[1]]=1;\n        int allNode = 0;\n        while(!q.isEmpty() && allNode<list.size()){\n            int[] node = q.poll();\n            int step = node[0];\n            int x = node[1];\n            int y = node[2];\n            String nodeString = x+"-"+y;\n            if(hmap.containsKey(nodeString)){\n                allNode++;\n                int p = hmap.get(nodeString);\n                dist[startNode][p] = step;\n            }\n            for(int[] d:dir){\n                int x1 = x+d[0];\n                int y1 = y+d[1];\n                if(x1>=0 && x1<50 && y1>=0 && y1<50 && vis[x1][y1]==0){\n                    vis[x1][y1]=1;\n                    q.add(new int[]{step+1,x1,y1});\n                }\n            }\n        }\n    }\n\n    public int fun(int node,int mask,int state){\n        if(mask==allMask){\n            return 0;\n        }\n        if(dp[node][mask][state]!=-1){\n            return dp[node][mask][state];\n        }\n        if(state==0){\n            int ans = 0;\n            for(int i=1;i<list.size();i++){\n                int actualNode = (i-1);\n                if(((mask>>actualNode)&1)==0){\n                    ans = Math.max(ans,dist[node][i]+fun(i,mask|(1<<actualNode),1));\n                }\n            }\n            return dp[node][mask][state] = ans;\n        }else{\n            int ans = (int)(1e9);\n            for(int i=1;i<list.size();i++){\n                int actualNode = (i-1);\n                if(((mask>>actualNode)&1)==0){\n                    ans = Math.min(ans,dist[node][i]+fun(i,mask|(1<<actualNode),0));\n                }\n            }\n            return dp[node][mask][state] = ans;\n        }\n    }\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        hmap = new HashMap<>();\n        list = new ArrayList<>();\n        String temp = kx+"-"+ky;\n        hmap.put(temp,0);\n        list.add(temp);\n        for(int i=0;i<positions.length;i++){\n            temp = positions[i][0]+"-"+positions[i][1];\n            hmap.put(temp,i+1);\n            list.add(temp);\n        }\n        int n = list.size();\n        dist = new int[n+1][n+1];\n        for(int i=0;i<n;i++){\n            find(i);\n        }\n        int m = list.size()-1;\n        allMask = (1<<m)-1;\n        dp = new int[n][allMask][2];\n        for(int i=0;i<n;i++){\n            for(int j=0;j<allMask;j++){\n                Arrays.fill(dp[i][j],-1);\n            }\n        }\n        return fun(0,0,0);\n    }\n}\n```
['Java']