JS | BFS + DFS With DP
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can split this question into two subproblems: \n- finding the number of moves it wou
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can split this question into two subproblems: \n- finding the number of moves it would take to move a knight between two pawns\n- a DFS trying all ways of moving between pawns (with DP)\n\nThe only really tricky thing here is finding the distance between two pawns. We can do a BFS starting at pawn A, until we find pawn B, as needed. This actually passes with memoization. However, it\'s a bit faster to do a fully BFS starting from each pawn, precomputing the cost for each pair of pawns.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Find the cost between each pair of pawns by doing a BFS starting at each pawn\n- Do a DFS from the starting position to each pawn, in all possible orders.\n  - Use DP so that we don\'t re-check redundant paths (i.e. pawn 1 -> 2 -> 3 -> ..., then 2 -> 1 -> 3 -> ...)\n\n# Code\n```javascript []\n/**\n * @param {number} kx\n * @param {number} ky\n * @param {number[][]} positions\n * @return {number}\n */\nvar maxMoves = function(kx, ky, positions) {\n    //alice goes first\n    //alice wants to maximize result\n\n    //add the starting position\n    positions.unshift([kx, ky]);\n\n    let dp = new Float64Array(positions.length * (2**positions.length));\n    let degreesBetweenPawnPairs = new Float64Array(positions.length * positions.length);\n\n    computeAllDegreesBetweenPawns();\n\n    //if the mask is equal to this, we\'ve visited all pawns\n    let targetMask = (1<<positions.length)-1;\n\n    //alice starts, so we set maximize to true\n    return dfs(0, true, 1);\n\n    function dfs(pawn1Idx, maximize, mask) {\n        if(mask === targetMask) { return 0; }\n\n        let dpIdx = pawn1Idx*(2**positions.length)\n                    + mask;\n        if(dp[dpIdx] > 0) { return dp[dpIdx]-1; }\n\n        let best = Infinity;\n        let worst = 0;\n\n        for(let pawn2Idx = 0; pawn2Idx < positions.length; ++pawn2Idx) {\n            if((mask & (1<<pawn2Idx))) { continue; }\n\n            let cur = degreeBetween(pawn1Idx, pawn2Idx);\n            cur += dfs(pawn2Idx, !maximize, mask | (1<<pawn2Idx));\n\n            best = Math.min(best, cur);\n            worst = Math.max(worst, cur);\n        }\n\n        let ret;\n        if(maximize) {\n            ret = worst;\n        } else {\n            ret = best;\n        }\n        \n        dp[dpIdx] = ret+1;\n        return ret;\n    }\n    \n\n    function computeAllDegreesBetweenPawns() {\n        let targets = new Map(positions.map(([x, y], idx) => [y*50+x, idx]));\n\n        let visited = new Array(50*50).fill(0);\n        const MOVES = [[2, 1], [-2, 1], [2, -1], [-2, -1], [1, -2], [1, 2], [-1, 2], [-1, -2]];\n\n        let seenCounts = new Array(positions.length).fill(1);\n\n        for(let i = 0; i < positions.length; ++i) {\n            let q = [positions[i]];\n            let q2 = [];\n            let steps = 0;\n\n\n            visited[positions[i][1]*50 + positions[i][0]] = i+1;\n\n            while(seenCounts[i] < positions.length) {\n                let [x, y] = q.pop();\n\n    \n                for(let [offx, offy] of MOVES) {\n                    let newX = x + offx;\n                    let newY = y + offy;\n    \n                    if(newX >= 50 || newY >= 50 || newX < 0 || newY < 0) { continue; }\n                    let visitedDpIdx = newY*50 + newX;\n                    if(visited[visitedDpIdx] === (i+1)) { continue; }\n\n                    {\n                        if(targets.has(visitedDpIdx)) {\n                            let v1 = i;\n                            let v2 = targets.get(visitedDpIdx);\n\n                            if(v2 > v1) {\n                                degreesBetweenPawnPairs[v1*positions.length + v2] = steps+1;\n                                degreesBetweenPawnPairs[v2*positions.length + v1] = steps+1;\n                                ++seenCounts[v2];\n                                ++seenCounts[v1];\n                            }\n                        }\n                    }\n\n                    visited[visitedDpIdx] = i+1;\n                    q2.push([newX, newY]);\n                }\n    \n                if(!q.length) {\n                    [q2, q] = [q, q2];\n                    ++steps;\n                }\n            }\n    \n        }\n    }\n\n\n    function degreeBetween(i, j) {\n        return degreesBetweenPawnPairs[i*positions.length + j];\n    }\n};\n\n```
['JavaScript']