PROBLEM LINK:
Author: Md Shahid
Tester: Arkapravo Ghosh
Editorialist: Md Shahid
DIFFICULTY:
EASY
PREREQUISITES:
Matrix, Dynamic programming
PROBLEM:
You have given two matrix, one is binary matrix and another is weight matrix.
 Binary matrix represents on which block you can step forward like you can only step upon block having zero.
 Weight matrix represents weights of each block
You need to find the minimum possible weighted path sum if present.
EXPLANATION:
Before we get into the problem, i want to introduce you a dynamic programming technique which you may or may not know.We will understand in following ways
 Algorithm (Path in a grid)
 Problem Solution
1. Path in a grid
Suppose you have matrix of size N x$N$. Each of the cell of matrix has a number assigned to it. Your task is to find the sum of path from position (1,1) to (N,N) such that sum is maximum possible. But there is one condition that you can only move down and right. For example 
3  2  1  0 
5  8  9  1 
0  1  10  11 
11  12  15  5 
In this case, the maximum possible distance is 55. The following describes the path on which we can get maximum possible sum.
3  
5  8  9  
10  
15  5 
1.1 Algorithm
Assume that the rows and columns of the grid are numbered from 1 to n, and value[y][x] equals the value of cell (y, x). Let sum(y, x) denote the maximum sum on a path from the upperleft corner to cell (y, x). Now sum(n,n) tells us the maximum sum from the upperleft corner to the lowerright corner. For example, in the above grid, sum(4,4) = 55.
We can recursively calculate the sums as follows:
sum(y, x) = max(sum(y, x−1),sum(y−1, x))+value[y][x]
The recursive formula is based on the observation that a path that ends at
square (y, x) can come either from square (y, x−1) or square (y−1, x)
Thus, we select the direction that maximizes the sum. We assume that
sum(y, x) = 0 if y = 0 or x = 0 (because no such paths exist), so the recursive
formula also works when y = 1 or x = 1.
Steps
 Initialized sum[N+1][N+1] = {0}
 Run a For loop fron i = 1 to i = N
 Again run a For loop fron j=1 to j=N
 sum(i, j) = max(sum(i, j−1),sum(i−1, j))+value[i][j]
 End For
 End For
 Return sum[N][N]
2. Problem Solution
Problem can be solved in following steps:

Check the possibility.

Find maximum possible path sum.
2.1 Check the possibility:
In first step you have to invert all the bits of your binary array. Inverting bits means, you have to make all zero to one and all one to zero. For example
Suppose you have binary matrix b[N][N] 
0  0  1  1 
0  0  0  1 
1  1  0  0 
0  1  0  0 
Inverted form $b[N][N]$
1  1  0  0 
1  1  1  0 
0  0  1  1 
1  0  1  1 
Reason for inverting the b[N][N] matrix is, we can apply recursive algorithm to check there exists a path or not.
2.1.1 Algorithm
 Initialized valid[N+1][N+1] = {0} and valid[0][1] = valid[1][0] = 1
 Run a For loop fron i = 1 to i = N
 Again run a For loop fron j=1 to j=N
 valid[i][j] = (valid[i1][j]  valid[i][j1]) && b[i][j]
 End For
 End For
 Return valid[N][N]
If the value of valid[N][N] is 1 i.e, there exist at least one path.
2.2 Find maximum possible path sum:
If the value of valid[N][N] is 1 i.e, there exist at least one path. If there exists path then run the recursive algorithm which is stated earlier to find maximum path sum keeping the track of b[N][N] matrix.
2.2.2 Algorithm
 Initialized dis[N+1][N+1] = {0}
 Run a For loop i = i to i = N
 Run another loop j = 1 to j = N
 If valid[i][j] == 1
 dis[i][j] = min(dis[i1][j], dis[i][j1]) + a[i][j] (where a is weight matrix)
 End If
 End For
 End For
 Print “Yes” and dis[N][N].
Complexity :
The time complexity of this algorithm is O(N^2) and space comlexity is O(N^2).
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.