Shortest Land Path
Problem statement
Given a square binary grid, find a shortest path from start to target using only land. A cell containing 0 is land; a cell containing 1 is water.
Both endpoint arrays are zero-based coordinates [row, column]. A move travels one cell up, down, left or right, stays inside the grid, and never enters water. Each move has equal cost.
Return the path as an ordered array of coordinates, including the start and target. Minimize the number of moves. If several shortest paths exist, return the lexicographically smallest coordinate sequence: compare the first differing coordinates by row, then column.
Return an empty array when either endpoint is water or the target is unreachable. When the endpoints are the same land cell, return that one coordinate. Do not modify the grid or endpoint arrays.
Function
shortestLandPath(grid: int[][], start: int[], target: int[]) → int[][]Examples
Example 1
grid = [[0,0,0],[1,1,0],[0,0,0]]start = [0,0]target = [2,0]return = [[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0]]The only land route follows the top row, descends along column 2, then moves left along the bottom row. It uses 6 moves and includes both endpoints.
Example 2
grid = [[0,0],[0,0]]start = [1,1]target = [0,0]return = [[1,1],[0,1],[0,0]]Both shortest routes use 2 moves. The route through [0,1] wins because that first differing coordinate is lexicographically smaller than [1,0].
Example 3
grid = [[0,0,0],[1,1,1],[0,0,0]]start = [0,0]target = [2,2]return = []The water row separates the endpoints. No land-only route exists, so the result is an empty array.
Constraints
1 <= n == grid.length <= 40.- Every row contains exactly
ncells, and every cell is0or1. start.length == target.length == 2; every coordinate is in0..n-1.- A returned path has at most
n^2coordinates.