Shortest Path in a Grid

Given a grid with R rows and C columns where each cell is either walkable (denoted by 0) or blocked (denoted by 1), find the shortest path from a start cell to an end cell. You can move in four directions: up, down, left, and right. If there is no valid path from the start to the end, output -1.

The grid can be mathematically represented as follows: For each cell \(grid[i][j]\), if \(grid[i][j] = 0\), the cell is walkable; if \(grid[i][j] = 1\), the cell is blocked.

inputFormat

The input is given via standard input and has the following format:

R C
row1
row2
...
rowR
sx sy ex ey

Where:

• R and C are integers representing the number of rows and columns in the grid respectively.
• Each of the next R lines contains C space-separated integers (either 0 or 1) representing a row of the grid.
• The last line contains four integers: sx sy ex ey, which denote the starting position (\(sx, sy\)) and the ending position (\(ex, ey\)).

outputFormat

Output a single integer to standard output: the length of the shortest path from the start cell to the end cell. If no such path exists, output -1.

4 4
0 0 1 0
0 0 0 0
0 1 0 1
1 0 0 0
0 0 3 3

6