Fewest Moves for a Chess Piece With Type-Specific Step Directions to Capture the King
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A board game is played on a rectangular grid. Your piece starts on one square and wins by capturing the opposing king, which it does by moving onto the king's square. Some squares hold blocking pieces, and your piece can never move onto them.
Pieces come in different types, and each type may step only in its own set of directions. The basic piece steps one square in any of the eight directions: up, down, left, right or one of the four diagonals. Another type might be limited to the four orthogonal directions, or to some other subset of the eight. Your piece's type is given to you as the set of directions it may step in.
Return the minimum number of moves your piece needs to capture the king, or `-1` if the king cannot be reached.
### Function Signature
```python
def min_moves_to_capture(board: list[str], directions: list[list[int]]) -> int:
```
`board[r][c]` is `'S'` for your piece's starting square, `'K'` for the king's square, `'#'` for a blocked square and `'.'` for an empty square. Row `0` is the top row and column `0` is the leftmost column.
`directions` lists the steps your piece may take, each as a pair `[dr, dc]`: `[1, 0]` steps one row down and `[0, 1]` steps one column right. The eight-direction piece is `directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]`.
### Rules
- From `(r, c)` a move leads to `(r + dr, c + dc)` for any `[dr, dc]` in `directions`, so every move covers exactly one square. The destination must be inside the board and must not be `'#'`.
- Only the listed directions are allowed. A piece that may step `[1, 0]` cannot step `[-1, 0]` unless that pair is also listed.
- A diagonal move is allowed whenever its destination is allowed, even if both squares beside the diagonal are blocked.
- The king never moves, and neither do the blocking pieces. The starting square is empty once your piece leaves it.
- Return the minimum number of moves after which your piece stands on the king's square, or `-1` if no sequence of moves gets there.
### Constraints
- `1 <= len(board) <= 500` and `1 <= len(board[0]) <= 500`; all rows have the same length.
- Every character is `'S'`, `'K'`, `'#'` or `'.'`.
- The board contains exactly one `'S'` and exactly one `'K'`.
- `1 <= len(directions) <= 8`. Each pair `[dr, dc]` has `dr` and `dc` in `{-1, 0, 1}`, not both `0`, and no pair appears twice.
### Examples
**Example 1**
```text
Input: board = ["S...",
".##.",
"...K"]
directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
Output: 4
```
The king is two rows down and three columns to the right. Three moves would require a step to the right every time, and because `(1, 1)` and `(1, 2)` are blocked, the piece would still be in row 0 after two moves and could not reach row 2 with the third. One four-move route is `(0, 0)`, `(0, 1)`, `(0, 2)`, `(1, 3)`, `(2, 3)`.
**Example 2**
```text
Input: board = ["S...",
".##.",
"...K"]
directions = [[-1, 0], [0, -1], [0, 1], [1, 0]]
Output: 5
```
With only the four orthogonal directions, each move changes either the row or the column by one, and the king is two rows and three columns away, so at least five moves are needed. One five-move route is `(0, 0)`, `(0, 1)`, `(0, 2)`, `(0, 3)`, `(1, 3)`, `(2, 3)`.
**Example 3**
```text
Input: board = ["S#",
"#K"]
directions = [[-1, 0], [0, -1], [0, 1], [1, 0]]
Output: -1
```
Both orthogonal neighbors of the start are blocked, so this piece cannot move at all. A piece whose directions include `[1, 1]` would capture the king in one move on this board, because a diagonal step is allowed even when both squares beside it are blocked.
Overview: On a grid with blocked squares, a chess piece must reach and capture the opposing king, stepping one square per move in only the directions its piece type allows, such as all eight neighbors or just the four orthogonal ones. The task asks for the fewest moves, or -1 if the king is unreachable, and tests shortest-path search on grids with a configurable move set.
Your piece starts on one square of a rectangular board and wins by capturing the opposing king, which it does by moving onto the king's square. Some squares hold blocking pieces, and your piece can never move onto them.
Pieces come in different types, and each type may step only in its own set of directions. The basic piece steps one square in any of the eight directions: up, down, left, right or one of the four diagonals. Another type might be limited to the four orthogonal directions, or to some other subset of the eight. Your piece's type is given to you as the list of directions it may step in.
Implement `min_moves_to_capture(board, directions)`: return the minimum number of moves your piece needs to capture the king, or `-1` if the king cannot be reached.
`board[r][c]` is `'S'` for your piece's starting square, `'K'` for the king's square, `'#'` for a blocked square and `'.'` for an empty square. Row `0` is the top row and column `0` is the leftmost column.
`directions` lists the steps your piece may take, each as a pair `[dr, dc]`: `[1, 0]` steps one row down and `[0, 1]` steps one column right. The eight-direction piece is `directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]`.
**Rules**
- From `(r, c)` a move leads to `(r + dr, c + dc)` for any `[dr, dc]` in `directions`, so every move covers exactly one square. The destination must be inside the board and must not be `'#'`.
- Only the listed directions are allowed. A piece that may step `[1, 0]` cannot step `[-1, 0]` unless that pair is also listed.
- A diagonal move is allowed whenever its destination is allowed, even if both squares beside the diagonal are blocked.
- The king never moves, and neither do the blocking pieces. The starting square is empty once your piece leaves it.
- Return the minimum number of moves after which your piece stands on the king's square, or `-1` if no sequence of moves gets there.
The answer is `-1` or at most `len(board) * len(board[0]) - 1` (at most 249,999), so it never exceeds 2^31 - 1 and a 32-bit `int` suffices in every language.
**Example 1**
```
Input: board = ['S...',
'.##.',
'...K']
directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
Output: 4
```
The king is two rows down and three columns to the right. Three moves would require a step to the right every time, and because `(1, 1)` and `(1, 2)` are blocked, the piece would still be in row 0 after two moves and could not reach row 2 with the third. One four-move route is `(0, 0)`, `(0, 1)`, `(0, 2)`, `(1, 3)`, `(2, 3)`.
**Example 2**
```
Input: board = ['S#',
'#K']
directions = [[-1, 0], [0, -1], [0, 1], [1, 0]]
Output: -1
```
Both orthogonal neighbors of the start are blocked, so this piece cannot move at all. A piece whose directions include `[1, 1]` would capture the king in one move on this board, because a diagonal step is allowed even when both squares beside it are blocked.
**Constraints**
- `1 <= len(board) <= 500` and `1 <= len(board[0]) <= 500`; all rows have the same length.
- Every character is `'S'`, `'K'`, `'#'` or `'.'`.
- The board contains exactly one `'S'` and exactly one `'K'`.
- `1 <= len(directions) <= 8`. Each pair `[dr, dc]` has `dr` and `dc` in `{-1, 0, 1}`, not both `0`, and no pair appears twice.
Constraints
- 1 <= len(board) <= 500 and 1 <= len(board[0]) <= 500; all rows have the same length.
- Every character is 'S', 'K', '#' or '.'.
- The board contains exactly one 'S' and exactly one 'K'.
- 1 <= len(directions) <= 8. Each pair [dr, dc] has dr and dc in {-1, 0, 1}, not both 0, and no pair appears twice.
Examples
Input: (['S...', '.##.', '...K'], [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]])
Expected Output: 4
Explanation: Source Example 1: a 3-move route must step right every move, but (1, 1) and (1, 2) are blocked, so 4 moves via (0, 1), (0, 2), (1, 3), (2, 3).
Input: (['S...', '.##.', '...K'], [[-1, 0], [0, -1], [0, 1], [1, 0]])
Expected Output: 5
Explanation: Source Example 2: orthogonal-only piece needs the Manhattan distance 2 + 3 = 5, achieved along the open top row and right column.
Hints
- Only the listed directions exist: being able to step from A to B does not mean you can step from B back to A, so think about where you can actually get to from the start.
- Whether a step is legal depends only on its destination square (inside the board and not '#'), never on the squares beside a diagonal.
- Every move covers exactly one square and counts the same. If the king is not among the squares your piece can ever reach, the answer is -1.