Determine Reachability for a Chinese-Chess Horse with Blocked Legs

Problem Statement

In Chinese chess (Xiangqi), the horse moves in an "L" shape similar to a chess knight, but with a crucial restriction called "hobbling the horse's leg" (蹩马腿).

From a square (r, c), the horse can move two units in one cardinal direction and one unit perpendicular, arriving at (r + dr, c + dc). However, the move is divided into two phases:

1. The horse first takes one orthogonal step to an adjacent square called the leg.
2. If the leg square is blocked by an obstacle or is off the board, the horse cannot move in that direction.
3. If the leg square is empty, the horse can continue diagonally to either of the two destination squares connected to that leg, provided the destination square is inside the board boundaries and is also not blocked by an obstacle.

Specifically, the 4 possible leg positions and their corresponding 2 destination endpoints are:

• Up leg (r - 1, c): destinations (r - 2, c - 1) and (r - 2, c + 1)
• Down leg (r + 1, c): destinations (r + 2, c - 1) and (r + 2, c + 1)
• Left leg (r, c - 1): destinations (r - 1, c - 2) and (r + 1, c - 2)
• Right leg (r, c + 1): destinations (r - 1, c + 2) and (r + 1, c + 2)

Given a 10 x 9 board represented as a 2D integer array where 0 denotes an empty square and 1 denotes an obstacle, write a function to return the minimum number of moves required to travel from start to target. If the target is unreachable, return -1.

Function Signature

def min_horse_moves(
    board: list[list[int]], 
    start: tuple[int, int], 
    target: tuple[int, int]
) -> int:
    pass

Constraints

• len(board) == 10
• len(board[0]) == 9
• board[r][c] in (0, 1)
• 0 <= start[0], target[0] < 10
• 0 <= start[1], target[1] < 9
• If start == target and board[start[0]][start[1]] == 0, the answer is 0.
• If board[target[0]][target[1]] == 1 or board[start[0]][start[1]] == 1, return -1.

Examples

Example 1

board = 10x9 grid of all 0s
start = (0, 0)
target = (2, 1)

Output: 1
Explanation: 
The leg is (1, 0), which is empty. The destination (2, 1) is empty and within bounds. The horse reaches the target in 1 move.

Example 2

board = 10x9 grid of all 0s except board[1][0] = 1
start = (0, 0)
target = (2, 1)

Output: -1
Explanation:
The direct move to (2, 1) requires passing through leg (1, 0), which is blocked. With all other paths examined, if no alternate route reaches (2, 1), it returns -1 (or more moves if another route exists).