Minimum number of flips required such that a Binary Matrix doesn 't contain any path from the top left to the bottom right consisting only of 0s | C ++ program for the above approach ; The four direction coordinates changes from the current cell ; Function that returns true if there exists any path from the top - left to the bottom - right cell of 0 s ; If the bottom - right cell is reached ; Update the cell to 1 ; Traverse in all four directions ; Find the new coordinates ; If the new cell is valid ; Recursively call DFS ; If path exists , then return true ; Return false , if there doesn 't  exists any such path ; Function to flip the minimum number of cells such that there doesn 't exists any such path from (0, 0) to (N - 1, M - 1) cell consisting of 0s ; Case 1 : If no such path exists already ; Case 2 : If there exists only one path ; Case 3 : If there exists two - path ; Driver Code
#include " bits / stdc + + . h " NEW_LINE using namespace std ; int direction [ ] [ 2 ] = { { -1 , 0 } , { 0 , 1 } , { 0 , -1 } , { 1 , 0 } } ; bool dfs ( vector < vector < int > > & matrix , int i , int j , int N , int M ) { if ( i == N - 1 and j == M - 1 ) { return true ; } matrix [ i ] [ j ] = 1 ; for ( int k = 0 ; k < 4 ; k ++ ) { int newX = i + direction [ k ] [ 0 ] ; int newY = j + direction [ k ] [ 1 ] ; if ( newX >= 0 and newX < N and newY > = 0 and newY < M and matrix [ newX ] [ newY ] == 0 ) { if ( dfs ( matrix , newX , newY , N , M ) ) { return true ; } } } return false ; } int solve ( vector < vector < int > > & matrix ) { int N = matrix . size ( ) ; int M = matrix [ 0 ] . size ( ) ; if ( ! dfs ( matrix , 0 , 0 , N , M ) ) { return 0 ; } if ( ! dfs ( matrix , 0 , 0 , N , M ) ) { return 1 ; } return 2 ; } int main ( ) { vector < vector < int > > mat = { { 0 , 1 , 0 , 0 } , { 0 , 1 , 0 , 0 } , { 0 , 0 , 0 , 0 } } ; cout << solve ( mat ) ; return 0 ; }