# Find Paths Across a Weighted Binary Grid Given an `m` by `n` binary grid, a cell with value `1` is traversable and `0` is blocked. Movement is allowed up, down, left, or right without leaving the grid. Implement three operations: 1. `has_top_to_bottom_path(grid)` returns whether any traversable cell in the first row can reach any traversable cell in the last row. 2. `all_simple_paths(grid)` returns every simple top-to-bottom path as a list of `(row, col)` coordinates. A simple path may not repeat a cell and terminates immediately when it first reaches any cell in the last row; it may not leave the last row and later return. Return paths in deterministic lexicographic order. 3. `shortest_weighted_path(grid, weights)` returns one minimum-cost top-to-bottom path, or an empty list if none exists. `weights[r][c]` is a positive cost paid when entering that cell, including the starting cell. Break equal-cost ties lexicographically by the full coordinate sequence. ## Constraints - `1 <= m, n <= 100` for reachability and shortest path. - `all_simple_paths` will be tested only when `m * n <= 20` because output can be exponential. - `weights` has the same shape as `grid` and contains positive integers. - When `m = 1`, every traversable first-row cell forms one singleton top-to-bottom path. ## Example For `[[1,0],[1,1]]`, a path is `[(0,0),(1,0)]`. With weights `[[4,9],[2,1]]`, that path costs `6`. ## Clarifications Discuss why BFS suffices for unweighted reachability, why enumerating all paths cannot be polynomial in the output size, and why positive nonuniform weights motivate Dijkstra's algorithm. ## Hints Treat every traversable cell as a graph vertex and add a virtual source connected to the first row. ## Extensions - Return only the number of simple paths. - Support diagonal moves. - Explain the change if weights can be zero or negative.