Given a path in the form of a rectangular matrix having few landmines arbitrarily placed (marked as 0), calculate length of the shortest safe route possible from any cell in the first column to any cell in the last column of the matrix. We have to avoid landmines and their four adjacent cells (left, right, above and below) as they are also unsafe. We are allowed to move to only adjacent cells which are not landmines. i.e. the route cannot contains any diagonal moves.

Example 1:
Input:
[1 0 1 1 1]
[1 1 1 1 1]
[1 1 1 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
Output: 6
Explanation:
We can see that length of shortest
safe route is 13 (Highlighted in Bold).
[1 0 1 1 1]
[1 1 1 1 1]
[1 1 1 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
Example 2:
Input:
[1 1 1 1 1]
[1 1 0 1 1]
[1 1 1 1 1]
Output: -1
Explanation: There is no possible path from
first column to last column.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findShortestPath() which takes matrix as input parameter and return an integer denoting the shortest path. If there is no possible path, return -1.
Expected Time Complexity: O(R * C)
Expected Auxiliary Space: O(1)
Constraints:
1 <= R,C <= 10^{3}

见题面

见题面