Move in Board: Determine Valid Moves for a Piece on a Game Board Given Obstacle Constraints

Question

## Problem

You have an `m x n` board. A piece is at position `(r, c)`. The board has obstacle cells marked `1`. A move is valid if the destination is within bounds and not an obstacle. Given a set of move directions, return all reachable cells in exactly `k` steps (no revisiting).

```python
def valid_moves(
    board: list[list[int]],
    start: tuple[int,int],
    k: int
) -> list[tuple[int,int]]:
    # Directions: up, down, left, right
    pass
```

**Example:**
```
board = [
  [0, 0, 1],
  [0, 0, 0],
  [1, 0, 0],
]
start = (0, 0), k = 2
output -> [(0,1),(1,0),(1,2),(2,1)]  # cells reachable in exactly 2 steps
```

## Follow-ups
1. Change from "exactly k steps" to "at most k steps" -- how does BFS layer tracking change?
2. The board is updated dynamically (obstacles appear and disappear). How do you invalidate cached reachability?
3. Extend moves to include knight-style jumps in addition to cardinal directions.
4. Find the minimum number of steps to reach a target cell, or -1 if unreachable.

Move in Board: Determine Valid Moves for a Piece on a Game Board Given Obstacle Constraints

Question Details

Full Details

Topics

More from Square/Block