Answer Repeated Shortest Increasing-Path Queries

Given an integer grid, repeatedly find a shortest strictly increasing path from the top-left cell to a requested target value. Moves are allowed up, right, down, and left. Return the values along the path, or an empty path if the target is absent or unreachable.

Implement increasing_paths(grid: int[][], targets: int[]) -> int[][], returning one value path per target in input order.

Constraints & Assumptions

• The grid is rectangular, with 1 through 100 rows and columns, and at most 1,000 target queries.
• Values are distinct signed 32-bit integers. The source does not specify duplicates; uniqueness is an explicit practice assumption so each target identifies one cell.
• A move is legal only if the next cell's value is strictly greater than the current value.
• Path length is measured in number of edges. The starting cell has a zero-edge path containing its own value.
• Resolve equal-length paths using the first discovery in a FIFO BFS that visits neighbors in this order: up, right, down, left. This is a deterministic tie convention for the source's any-shortest-path output.
• Preprocess the fixed grid once. Do not run a full new traversal for every query; each answer should require only lookup and output-path reconstruction after preprocessing.

Examples

grid = [[1,2,3],[4,5,8],[7,9,6]]
targets = [5,6,1]
result = [[1,2,5],[],[1]]

grid = [[4,3],[5,6]]
targets = [6,3,9]
result = [[4,5,6],[],[]]

Explain the preprocessing and per-query time and space costs. Compare storing a complete path at every reachable cell with storing one distance/predecessor per cell, including the cost of actually returning a long path. Discuss why a shortest-path traversal or equivalent dynamic program can reuse work across calls.