3283. Maximum Number of Moves to Kill All Pawns LeetCode Solution
In this guide, you will get 3283. Maximum Number of Moves to Kill All Pawns LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Moves to Kill All Pawns problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Moves to Kill All Pawns
There is a 50 x 50 chessboard with one knight and some pawns on it. You are given two integers kx and ky where (kx, ky) denotes the position of the knight, and a 2D array positions where positions[i] = [xi, yi] denotes the position of the pawns on the chessboard.
Alice and Bob play a turn-based game, where Alice goes first. In each player’s turn:
The player selects a pawn that still exists on the board and captures it with the knight in the fewest possible moves. Note that the player can select any pawn, it might not be one that can be captured in the least number of moves.
In the process of capturing the selected pawn, the knight may pass other pawns without capturing them. Only the selected pawn can be captured in this turn.
Alice is trying to maximize the sum of the number of moves made by both players until there are no more pawns on the board, whereas Bob tries to minimize them.
Return the maximum total number of moves made during the game that Alice can achieve, assuming both players play optimally.
Note that in one move, a chess knight has eight possible positions it can move to, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.
Alice picks the pawn at (2, 2) and captures it in two moves: (0, 2) -> (1, 4) -> (2, 2).
Bob picks the pawn at (3, 3) and captures it in two moves: (2, 2) -> (4, 1) -> (3, 3).
Alice picks the pawn at (1, 1) and captures it in four moves: (3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1).
Alice picks the pawn at (2, 4) and captures it in two moves: (0, 0) -> (1, 2) -> (2, 4). Note that the pawn at (1, 2) is not captured.
Bob picks the pawn at (1, 2) and captures it in one move: (2, 4) -> (1, 2).
Constraints:
0 <= kx, ky <= 49
1 <= positions.length <= 15
positions[i].length == 2
0 <= positions[i][0], positions[i][1] <= 49
All positions[i] are unique.
The input is generated such that positions[i] != [kx, ky] for all 0 <= i < positions.length.
Complexity Analysis
Time Complexity: O(n \cdot 50^2 + n^2 \cdot 2^n)
Space Complexity: O(n^2 + n \cdot 2^n) = O(n \cdot 2^n)
3283. Maximum Number of Moves to Kill All Pawns LeetCode Solution in C++
class Solution {
public:
int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
const int n = positions.size();
positions.push_back({kx, ky});
unordered_map<int, int> hashedPositionToIndex;
// dist[i][j] := the minimum distance from positions[i] to positions[j]
vector<vector<int>> dist(n + 1, vector<int>(n + 1));
for (int i = 0; i < positions.size(); ++i) {
const int x = positions[i][0];
const int y = positions[i][1];
hashedPositionToIndex[hash(x, y)] = i;
}
for (int sourceIndex = 0; sourceIndex < n + 1; ++sourceIndex)
bfs(positions, sourceIndex, hashedPositionToIndex, dist);
const int maxMask = 1 << (n + 1);
// dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
// kill all pawns, where i is the current pawn, mask is the set of pawns
// that have been killed, and turn is the current player's turn (0 for Alice
// and 1 for Bob)
vector<vector<vector<int>>> dp(
n + 1, vector<vector<int>>(1 << (n + 1), vector<int>(2)));
for (int i = 0; i < n + 1; ++i)
for (int mask = 0; mask < maxMask - 1; ++mask)
dp[i][mask] = {-kMax, kMax};
for (int mask = maxMask - 2; mask >= 0; --mask)
for (int i = 0; i < n + 1; ++i)
for (int turn = 0; turn < 2; ++turn)
for (int j = 0; j < n; ++j) {
if (mask >> j & 1)
continue;
const int moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn];
dp[i][mask][turn] = turn == 0 ? max(dp[i][mask][turn], moves)
: min(dp[i][mask][turn], moves);
}
// Returns the maximum cost to kill all pawns, i.e., the original positions
// array without the knight (kx, ky).
return dp[n][1 << n][0];
}
private:
static constexpr int kSize = 50;
static constexpr int kMax = 1'000'000;
static constexpr int dirs[8][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
int hash(int x, int y) {
return x * kSize + y;
}
// Computes the distance between positions[sourceIndex] and other positions.
void bfs(const vector<vector<int>>& positions, int sourceIndex,
const unordered_map<int, int>& hashedPositionToIndex,
vector<vector<int>>& dist) {
const int sx = positions[sourceIndex][0];
const int sy = positions[sourceIndex][1];
queue<pair<int, int>> q{{{sx, sy}}};
vector<vector<bool>> seen(kSize, vector<bool>(kSize));
seen[sx][sy] = true;
int seenPositions = 0;
for (int step = 0; !q.empty() && seenPositions < positions.size(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
if (const auto it = hashedPositionToIndex.find(hash(i, j));
it != end(hashedPositionToIndex)) {
dist[sourceIndex][it->second] = step;
++seenPositions;
}
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x >= kSize || y < 0 || y >= kSize)
continue;
if (seen[x][y])
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
}
}; /* code provided by PROGIEZ */
3283. Maximum Number of Moves to Kill All Pawns LeetCode Solution in Java
class Solution {
public int maxMoves(int kx, int ky, int[][] positions) {
final int n = positions.length;
List<int[]> positionsList = new ArrayList<>(List.of(positions));
positionsList.add(new int[] {kx, ky});
Map<Integer, Integer> hashedPositionToIndex = new HashMap<>();
// dist[i][j] := the minimum distance from positions[i] to positions[j]
int[][] dist = new int[n + 1][n + 1];
for (int i = 0; i < positionsList.size(); ++i) {
final int x = positionsList.get(i)[0];
final int y = positionsList.get(i)[1];
hashedPositionToIndex.put(hash(x, y), i);
}
for (int sourceIndex = 0; sourceIndex < n + 1; ++sourceIndex)
bfs(positionsList, sourceIndex, hashedPositionToIndex, dist);
int kMaxMask = 1 << (n + 1);
// dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
// kill all pawns, where i is the current pawn, mask is the set of pawns
// that have been killed, and turn is the current player's turn (0 for Alice
// and 1 for Bob)
int[][][] dp = new int[n + 1][1 << (n + 1)][2];
for (int i = 0; i < n + 1; ++i)
for (int mask = 0; mask < kMaxMask - 1; ++mask)
dp[i][mask] = new int[] {-kMax, kMax};
for (int mask = kMaxMask - 2; mask >= 0; --mask)
for (int i = 0; i < n + 1; ++i)
for (int turn = 0; turn < 2; ++turn)
for (int j = 0; j < n; ++j) {
if ((mask >> j & 1) == 1)
continue;
final int moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn];
dp[i][mask][turn] = turn == 0 ? Math.max(dp[i][mask][turn], moves) //
: Math.min(dp[i][mask][turn], moves);
}
// Returns the maximum cost to kill all pawns, i.e., the original positions
// array without the knight (kx, ky).
return dp[n][1 << n][0];
}
private static final int kSize = 50;
private static final int kMax = 1_000_000;
private static final int[][] dirs = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
private int hash(int x, int y) {
return x * kSize + y;
}
// Computes the distance between positions[sourceIndex] and other positions.
private void bfs(List<int[]> positions, int sourceIndex,
Map<Integer, Integer> hashedPositionToIndex, int[][] dist) {
final int sx = positions.get(sourceIndex)[0];
final int sy = positions.get(sourceIndex)[1];
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(sx, sy)));
boolean[][] seen = new boolean[kSize][kSize];
seen[sx][sy] = true;
int seenPositions = 0;
for (int step = 0; !q.isEmpty() && seenPositions < positions.size(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
final int hashedPosition = hash(i, j);
if (hashedPositionToIndex.containsKey(hashedPosition)) {
dist[sourceIndex][hashedPositionToIndex.get(hashedPosition)] = step;
++seenPositions;
}
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x >= kSize || y < 0 || y >= kSize)
continue;
if (seen[x][y])
continue;
q.offer(new Pair<>(x, y));
seen[x][y] = true;
}
}
}
} // code provided by PROGIEZ
3283. Maximum Number of Moves to Kill All Pawns LeetCode Solution in Python
class Solution:
def __init__(self):
self.kSize = 50
self.kMax = 1_000_000
self.dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2))
def maxMoves(self, kx: int, ky: int, positions: list[list[int]]) -> int:
n = len(positions)
positions.append([kx, ky])
hashedPositionToIndex = {}
# dist[i][j] := the minimum distance from positions[i] to positions[j]
dist = [[0] * (n + 1) for _ in range(n + 1)]
for i, (x, y) in enumerate(positions):
hashedPositionToIndex[self._hash(x, y)] = i
for sourceIndex in range(n + 1):
self._bfs(positions, sourceIndex, hashedPositionToIndex, dist)
kMaxMask = 1 << (n + 1)
# dp[i][mask][turn] := the maximum (Alice) or the minimum (Bob) cost to
# kill all pawns, where i is the current pawn, mask is the set of pawns
# that have been killed, and turn is the current player's turn (0 for Alice
# and 1 for Bob)
dp = [[[0, 0]
for _ in range(1 << (n + 1))]
for _ in range(n + 1)]
for i in range(n + 1):
for mask in range(kMaxMask - 1):
dp[i][mask] = [-self.kMax, self.kMax]
for mask in range(kMaxMask - 2, -1, -1):
for i in range(n + 1):
for turn in range(2):
for j in range(n):
if mask >> j & 1:
continue
moves = dist[i][j] + dp[j][mask | 1 << j][1 - turn]
dp[i][mask][turn] = (max(dp[i][mask][turn], moves) if turn == 0 else
min(dp[i][mask][turn], moves))
# Returns the maximum cost to kill all pawns, i.e., the original positions
# array without the knight (kx, ky).
return dp[n][1 << n][0]
def _hash(self, x: int, y: int) -> int:
return x * self.kSize + y
def _bfs(
self,
positions: list[list[int]],
sourceIndex: int,
hashedPositionToIndex: dict[int, int],
dist: list[list[int]]
) -> None:
"""
Computes the distance between positions[sourceIndex] and other positions.
"""
sx, sy = positions[sourceIndex]
q = collections.deque([(sx, sy)])
seen = {(sx, sy)}
seenPositions = 0
step = 0
while q and seenPositions < len(positions):
for _ in range(len(q)):
i, j = q.popleft()
hashedPosition = self._hash(i, j)
if hashedPosition in hashedPositionToIndex:
dist[sourceIndex][hashedPositionToIndex[hashedPosition]] = step
seenPositions += 1
for dx, dy in self.dirs:
x = i + dx
y = j + dy
if x < 0 or x >= self.kSize or y < 0 or y >= self.kSize:
continue
if (x, y) in seen:
continue
q.append((x, y))
seen.add((x, y))
step += 1 # code by PROGIEZ
