Determine Reachability for a Chinese-Chess Horse with Blocked Legs
Implement a function that determines whether a Chinese-chess horse can reach a target square from a starting square on a standard 10-row by 9-column board. Some squares contain obstacles. An obstacle cannot be occupied, and it can also block the horse's “leg.” The horse may make any number of legal moves.
Function Signature
def can_reach(start: list[int], target: list[int], blocked: list[list[int]]) -> bool:
Inputs
-
start
is
[row, column]
for the initial square.
-
target
is
[row, column]
for the destination square.
-
blocked
contains distinct obstacle coordinates.
-
Rows are numbered
0
through
9
; columns are numbered
0
through
8
.
-
start
and
target
are valid board coordinates and are not blocked.
Movement Rules
A horse move changes position by two squares along one axis and one square along the other axis. For a move with a two-row change, the orthogonally adjacent square one row toward the destination is the leg square. For a move with a two-column change, the orthogonally adjacent square one column toward the destination is the leg square. The move is legal only when the destination is on the board, the destination is not blocked, and the leg square is not blocked.
Output
Return True if the target is reachable by zero or more legal moves; otherwise return False.
Constraints
-
0 <= len(blocked) <= 88
-
All coordinates in
blocked
are unique and valid.
-
The input collections must not be mutated.
Examples
start = [0, 0]
target = [2, 1]
blocked = []
output = True
start = [0, 0]
target = [2, 1]
blocked = [[1, 0], [0, 1]]
output = False
In the second example, both possible first-move directions from the corner have blocked leg squares.