Implement BFS-based maze solver

# Maze Printing and BFS Solver You are given a 2D grid representing a maze. Each cell of the grid is one of: - `'#'` – wall (cannot be passed) - `'.'` – empty path (can be passed) - `'S'` – start position (exactly one in the grid) - `'E'` – exit position (exactly one in the grid) You need to complete two related tasks. --- ## Task 1 – Correctly Print the Maze You are given a function with the following conceptual behavior: - Input: a 2D array `grid` of characters with `R` rows and `C` columns. - Output: print a textual representation of the maze to standard output. Requirements: - Print the maze row by row from top to bottom. - Within each row, print cells from left to right without extra spaces. - After each row, print a newline character. - Do not print an extra blank line at the end. Example input grid (shown here as a matrix): - Row 0: `['#', '#', '#', '#']` - Row 1: `['#', 'S', '.', '#']` - Row 2: `['#', '.', 'E', '#']` - Row 3: `['#', '#', '#', '#']` Expected output to stdout: ``` #### #S.# #.E# #### ``` The existing implementation has a bug and prints the maze incorrectly (for example, transposed rows/columns, missing newlines, or extra spaces). Describe how you would implement or fix the printing logic to satisfy the above specification. Assume constraints: - 1 ≤ R, C ≤ 200 - The grid always contains exactly one 'S' and one 'E'. --- ## Task 2 – Find the Shortest Path Using BFS Implement a function with the following behavior: - Input: the same 2D character grid. - Output: the length of the shortest path (in number of steps) from 'S' to 'E', moving only in 4 directions (up, down, left, right) and only through cells that are not walls (`'#'`). If there is no path, return -1. More formally: - You start on the cell containing 'S'. - In one move, you may move to an adjacent cell (up, down, left, or right) that is within bounds and not a wall. - Reaching the cell containing 'E' ends the path. - The path length is the number of moves taken. Example: Using the previous 4×4 grid: ``` #### #S.# #.E# #### ``` One valid shortest path is: - (1,1) 'S' → (2,1) '.' → (2,2) 'E' The shortest path length is 2, so the function should return 2. You may be asked to implement this in stages (first only detect reachability, then return distance, then optionally reconstruct the actual path), but the final requirement is to return the shortest path length. State the algorithm you would use (time and space complexity) and how you would implement it robustly for the given constraints.