Grid Maze (multi-part questions)

Grid Maze (multi-part) You are given an m x n grid grid where: 0 means the cell is free 1 means the cell is blocked You are also given a start S = (sr, sc) and a target T = (tr, tc) (both are within bounds and guaranteed to be 0). You may move in 4 directions (up/down/left/right) to adjacent cells, without leaving the grid or entering blocked cells. Answer the following 4 sub-questions. Q1: Reachability Determine whether T is reachable from S. Output: true/false Q2: Shortest distance If reachable, return the minimum number of steps from S to T (each move costs 1). If not reachable, return -1. Output: integer Q3: Return one shortest path If reachable, return any shortest path from S to T as a list of coordinates: [(r0,c0), (r1,c1), ..., (rk,ck)] where (r0,c0)=S and (rk,ck)=T and consecutive coordinates must be 4-neighbor adjacent. Output: coordinate sequence; if unreachable output an empty list [] Q4: Count the number of shortest paths Return the number of distinct shortest paths from S to T. Two paths are different if they differ at any position. Output: integer; if unreachable output 0 Input format (for the coding prompt) Read from stdin: Line 1: m n Next m lines: n integers (0/1) separated by spaces Next line: sr sc Next line: tr tc Next line: an integer q indicating which sub-question to answer (1-4) Output format If q=1: print true or false If q=2: print the shortest distance or -1 If q=3: print the path as r0,c0 r1,c1 ... rk,ck; if unreachable print an empty line If q=4: print the number of shortest paths Constraints 1 <= m, n <= 200 grid[i][j] in {0,1} Aim for O(m*n) time for each sub-question (Q4 can be done during layered BFS). Example Input 3 3 0 0 0 1 1 0 0 0 0 0 0 2 2 1 Output true