💥 Memory beats 100% [EXPLAINED]
IntuitionThe problem involves calculating the maximum number of moves a knight can make on a chessboard while trying to capture pawns. The knight starts at a gi
# Intuition
The problem involves calculating the maximum number of moves a knight can make on a chessboard while trying to capture pawns. The knight starts at a given position and needs to strategically capture pawns, either maximizing or minimizing the number of moves based on the player's turn.

# Approach
Calculate the shortest distance between the knight and each pawn using BFS (Breadth-First Search), and then use a minimax algorithm with dynamic programming (DP) to determine the optimal moves for each player while considering all possible states (whether a pawn is captured or not). We keep track of the DP states in a 2D array, where each entry stores the best result for a given position and set of captured pawns.

# Complexity
- Time complexity:
O(n^2 * 50^2), where n is the number of pawns. This comes from calculating distances for all pairs of positions using BFS, which runs in O(50^2) due to the grid size. After that, the minimax function explores all possible states with a depth of O(n) and at each level, checks O(n) possible moves.

- Space complexity:
O(n * 50^2), where n is the number of pawns. This is for storing the distance matrix and the DP table, which requires O(n^2) space for distances and O(n * 2^n) space for the DP table, where 2^n represents the possible states of captured pawns.

# Code
```kotlin []
class Solution {

    val INF = 1e9.toInt()
    val directions = listOf(
        Pair(2, 1), Pair(2, -1), Pair(-2, 1), Pair(-2, -1),
        Pair(1, 2), Pair(1, -2), Pair(-1, 2), Pair(-1, -2)
    )

    // BFS to calculate shortest path for knight
    fun bfs(startX: Int, startY: Int, endX: Int, endY: Int): Int {
        val dist = Array(50) { IntArray(50) { INF } }
        val q: ArrayDeque<Pair<Int, Int>> = ArrayDeque()
        q.add(Pair(startX, startY))
        dist[startX][startY] = 0

        while (q.isNotEmpty()) {
            val (x, y) = q.removeFirst()
            for ((dx, dy) in directions) {
                val nx = x + dx
                val ny = y + dy
                if (nx in 0 until 50 && ny in 0 until 50 && dist[nx][ny] == INF) {
                    dist[nx][ny] = dist[x][y] + 1
                    q.add(Pair(nx, ny))
                }
            }
        }
        return dist[endX][endY]
    }

    // Minimax DP with memoization
    fun minimax(currentKnightPos: Int, mask: Int, isAlice: Boolean, dist: Array<IntArray>, dp: Array<IntArray>): Int {
        if (mask == (1 shl dist.size) - 1) return 0 // All pawns captured
        if (dp[currentKnightPos][mask] != -1) return dp[currentKnightPos][mask]

        var res = if (isAlice) -INF else INF
        for (i in dist.indices) {
            if (mask and (1 shl i) == 0) { // If pawn i is not captured
                val nextMask = mask or (1 shl i)
                val moves = dist[currentKnightPos][i]
                if (isAlice) {
                    res = maxOf(res, moves + minimax(i, nextMask, !isAlice, dist, dp))
                } else {
                    res = minOf(res, moves + minimax(i, nextMask, !isAlice, dist, dp))
                }
            }
        }

        dp[currentKnightPos][mask] = res
        return res
    }

    fun maxMoves(kx: Int, ky: Int, positions: Array<IntArray>): Int {
        val n = positions.size

        // Calculate distances between the knight's position and each pawn
        val dist = Array(n) { IntArray(n) }
        for (i in 0 until n) {
            dist[i][i] = bfs(kx, ky, positions[i][0], positions[i][1])
            for (j in i + 1 until n) {
                val moves = bfs(positions[i][0], positions[i][1], positions[j][0], positions[j][1])
                dist[i][j] = moves
                dist[j][i] = moves // Separate assignment for both directions
            }
        }

        // DP table initialized with -1 (unvisited states)
        val dp = Array(n) { IntArray(1 shl n) { -1 } }

        // Start minimax from the knight's initial position
        var maxMoves = -INF
        for (i in 0 until n) {
            val moves = bfs(kx, ky, positions[i][0], positions[i][1])
            maxMoves = maxOf(maxMoves, moves + minimax(i, 1 shl i, false, dist, dp))
        }

        return maxMoves
    }
}

```
['Math', 'Dynamic Programming', 'Bit Manipulation', 'Breadth-First Search', 'Memoization', 'Heap (Priority Queue)', 'Game Theory', 'Shortest Path', 'Bitmask', 'Kotlin']