Grid Maze Multi-Part Shortest Path (with Wall Breaking Cross Bomb)

Maze Shortest Path (5-step progression, Q5 adds a “cross bomb” to break walls) You are given a maze grid grid where: 0 = empty cell (walkable) 1 = wall (blocked unless it gets destroyed) You are also given a start cell S = (sr, sc) and a target cell T = (tr, tc). In one step, you may move up/down/left/right by one cell without leaving the grid. Answer the following 5 sub-questions. Each question asks for the minimum number of steps from S to T (return -1 if unreachable): Q1: Basic shortest path Walls are not passable. Compute the minimum steps. Q2: Return one shortest path In addition to the minimum steps, return any one shortest path (either a list of coordinates or a direction string). If unreachable, return empty. Q3: Count the number of shortest paths Return the number of distinct shortest paths from S to T, modulo 1_000_000_007. Q4: Allow eliminating up to k walls Given an integer k, you may treat up to k wall cells as empty while traversing them (each wall cell traversed consumes 1). Compute the minimum steps. Q5: Add bombs (cross-shaped wall destruction) Instead of wall elimination, you have b bombs. At any time, you may detonate one bomb at your current cell. The detonation permanently turns walls into empty cells in a cross shape centered at your current cell: Affected cells include the center, and cells extending up/down/left/right. By default, the bomb affects the entire rays until the grid boundary (i.e., all cells in the same row/column aligned with the center). Destroyed walls become empty permanently and can be used later. Detonating a bomb costs one bomb; whether detonation costs a step depends on the interviewer—state your assumption. Under these rules, compute the minimum steps from S to T or -1 if unreachable. Constraints (suggested) 1 <= m, n <= 200 0 <= k, b <= 20 Examples Example 1: grid = [[0,0,0],[1,1,0],[0,0,0]] S=(0,0), T=(2,2) Output: 4 Example 2 (with wall eliminations): same grid k=1 Output: 4 Example 3 (unreachable): grid=[[0,1],[1,0]], S=(0,0), T=(1,1) Output: -1 Note: The original post only clearly mentions “a common maze problem with 5 sub-questions, and Q5 adds a cross bomb that breaks walls.” The above is a fully-specified interview-ready version; adjust details (e.g., limited cross length, whether detonation costs steps) if your original rules differ. Example Input 3 3 000 110 000 0 0 2 2 0 Output 4