Shortest Path in a Grid

You are given a grid of size R × C consisting of 0s and 1s, where 0 represents an open cell and 1 represents an obstacle. You are also given the starting cell and the destination cell (both 0-indexed). Your task is to find the shortest path from the start to the destination using only the four cardinal directions (up, down, left, right). If there is no valid path then output -1.

The length of a path is defined as the number of moves from the starting cell to the destination cell. In mathematical terms, the Manhattan distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is given by \( |x_1 - x_2| + |y_1 - y_2| \), and the shortest path minimizes the number of steps taken.

inputFormat

The input is given via standard input (stdin) as follows:

• The first line contains two integers R and C representing the number of rows and columns of the grid.
• The next R lines each contain C space-separated integers (either 0 or 1) representing the grid.
• The following line contains two integers representing the starting cell's row and column.
• The last line contains two integers representing the destination cell's row and column.

outputFormat

If a valid path exists, output the coordinates of each cell in the path in order, with each coordinate on a separate line in the format "row col". If there is no valid path, output -1.

## sample

3 3
0 0 0
0 0 0
0 0 0
0 0
2 2

0 0
0 1
0 2
1 2
2 2

</p>