Problem of the day
1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.
1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are
X 0 X X 0 X
X X X X 1 X
1 1 1 X X X
The length of the shortest path is 5.
The first line of input contains two integers 'N' and 'M' separated by a single space representing the number of rows and columns in the binary matrix respectively.
The next 'N' lines of the input contain 'M' single space-separated integers each representing the 'i'-th row of the Binary Matrix.
The next line of input contains two single space-separated integers 'SOURCEX' and 'SOURCEY' representing the coordinates of the source cell.
The next line of input contains two single space-separated integers 'DESTX' and 'DESTY' representing the coordinates of the destination cell.
1 <= N <= 500
1 <= M <= 500
MAT[i] = {0, 1}
0 <= SOURCEX <= N - 1
0 <= SOURCEY <= M - 1
0 <= DESTX <= N - 1
0 <= DESTY <= M - 1
MAT[SOURCEX][SOURCEY] = 1
Time Limit: 1 sec
For each test case, print a single line that contains a single integer i.e. length of the shortest path from the source cell to the destination cell.
You do not need to print anything; it has already been taken care of. Just implement the given function.
3 3
0 1 0
0 0 1
1 1 1
2 0
1 2
4
The shortest path is composed of the cells (2,0) -> (2,1) -> (2,2) -> (1,2). Length of this path is 4.
4 4
1 0 1 0
0 1 0 1
1 0 1 0
0 0 1 0
0 0
3 2
-1