Paths Between Numbers in a 3×3 Grid
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
The fixed grid is:
1 2 3
4 5 6
7 8 9Given distinct values startValue and targetValue, enumerate paths from the start to the target without visiting a cell more than once.
- Up, down, left, and right moves are always allowed.
- When
allowDiagonalis true, the four diagonal moves are also allowed. - When
shortestOnlyis true, return only paths with the minimum number of moves.
Serialize a path by joining its visited values with hyphens, and return all serialized paths in lexicographic order.
Function
enumerateGridPaths(startValue: int, targetValue: int, allowDiagonal: boolean, shortestOnly: boolean) → String[]Examples
Example 1
startValue = 1targetValue = 2allowDiagonal = falseshortestOnly = falsereturn = ["1-2","1-4-5-2","1-4-5-6-3-2","1-4-5-8-9-6-3-2","1-4-7-8-5-2","1-4-7-8-5-6-3-2","1-4-7-8-9-6-3-2","1-4-7-8-9-6-5-2"]These are all eight simple orthogonal paths from cell 1 to adjacent cell 2.
Example 2
startValue = 1targetValue = 9allowDiagonal = trueshortestOnly = truereturn = ["1-5-9"]Two diagonal moves through the center form the unique shortest path.
Example 3
startValue = 1targetValue = 3allowDiagonal = falseshortestOnly = truereturn = ["1-2-3"]The top-row route is the only two-move orthogonal path.
Constraints
1 <= startValue,targetValue <= 9.startValue != targetValue.