Maze Shortest Path

You are given a maze in the form of an $n\times n$ grid, where each cell is either 1 (open) or 0 (blocked). Your task is to find the shortest path from the top-left corner (0, 0) to the bottom-right corner $(n-1, n-1)$ by moving only in the four cardinal directions: up, down, left, and right. If a valid path exists, output a grid of the same dimensions with the cells along the path marked as 1 and all other cells as 0. If no such path exists, output -1.

Note: The shortest path is defined as the path with the minimum number of moves, and you must use the Breadth-First Search (BFS) strategy to ensure the optimal solution.

inputFormat

The first line of the input contains an integer $n$ ($1 \le n \le 100$), representing the dimensions of the maze. The next $n$ lines each contain $n$ integers separated by spaces, where each integer is either 0 or 1. Here, 1 indicates an open cell and 0 indicates an obstacle.

outputFormat

If a valid path exists, output $n$ lines with $n$ integers each (separated by a single space), representing the maze with the shortest path marked by 1s and all other cells marked by 0s. If no valid path exists, output -1.## sample

4
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1