FastPrep
Problem · Matrix

Xiangqi Horse Reachability

Learn this problem
● MediumeBayPHONE SCREEN

Problem statement

You control one horse on a standard Xiangqi board with 10 rows and 9 columns. A position is written as [row, column], using zero-based coordinates.

The horse may make any number of moves. Each move travels two cells along one axis and one cell along the other axis. Before reaching its destination, the horse passes an orthogonally adjacent horse-leg square in the direction of the two-cell part of the move.

A move is legal only when all of these conditions hold:

  • The destination is inside the board.
  • The destination is not an obstacle.
  • The horse-leg square is not an obstacle.

Given start, target, and all obstacles, return true if some legal sequence of moves reaches target. Otherwise, return false.

Function

canHorseReach(start: int[], target: int[], obstacles: int[][]) → boolean

Examples

Example 1

start = [0,0]target = [2,1]obstacles = []return = true

The horse can move directly from [0,0] to [2,1]. Its horse-leg square is [1,0], which is free.

Example 2

start = [0,0]target = [2,1]obstacles = [[1,0],[0,1]]return = false

From the corner, every in-bounds move uses either [1,0] or [0,1] as its horse-leg square. Both squares are obstacles, so the horse cannot make any move.

Example 3

start = [0,0]target = [2,1]obstacles = [[1,0]]return = true

The obstacle at [1,0] blocks the direct move, but a detour remains: [0,0], [1,2], [3,3], [2,1].

Constraints

  • start.length == 2 and target.length == 2.
  • Every position is a valid zero-based coordinate with 0 <= row < 10 and 0 <= column < 9.
  • start and target are distinct.
  • 0 <= obstacles.length <= 88.
  • Obstacle positions are unique, and neither start nor target is an obstacle.
drafts saved locally
public boolean canHorseReach(int[] start, int[] target, int[][] obstacles) {
    // write your code here
}
start[0,0]
target[2,1]
obstacles[]
expectedtrue
checking account