Maze Shortest Path

Given a 2D maze represented as a grid of integers, where 0 represents an open cell and 1 represents a wall, your task is to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). The path should be output as a sequence of coordinates in order, where each coordinate is a pair of integers (row, column). If no such path exists, output -1.

This problem can be efficiently solved using the Breadth-First Search (BFS) algorithm. At each step, you can move right, down, left, or up. The input first provides two integers representing the dimensions of the maze, followed by the maze grid itself.

Example:
For the maze:

3 3
0 0 1
1 0 0
1 1 0

The output should be:

0 0
0 1
1 1
1 2
2 2

If no valid path exists, simply print -1.

inputFormat

The first line contains two integers m and n, where m is the number of rows and n is the number of columns. This is followed by m lines each containing n integers separated by spaces (each integer is either 0 or 1) that represent the maze.

outputFormat

If a path exists, output each coordinate of the path on a new line with the row and column separated by a space. If no valid path exists, output -1.## sample

1 1
0

0 0