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 | 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
direction = [ [ - 1 , 0 ] , [ 0 , 1 ] , [ 0 , - 1 ] , [ 1 , 0 ] ] NEW_LINE def dfs ( i , j , N , M ) : NEW_LINE INDENT global matrix NEW_LINE if ( i == N - 1 and j == M - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT matrix [ i ] [ j ] = 1 NEW_LINE for k in range ( 4 ) : NEW_LINE INDENT newX = i + direction [ k ] [ 0 ] NEW_LINE newY = j + direction [ k ] [ 1 ] NEW_LINE if ( newX >= 0 and newX < N and newY >= 0 and newY < M and matrix [ newX ] [ newY ] == 0 ) : NEW_LINE INDENT if ( dfs ( newX , newY , N , M ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def solve ( ) : NEW_LINE INDENT global matrix NEW_LINE N = len ( matrix ) NEW_LINE M = len ( matrix [ 0 ] ) NEW_LINE if ( not dfs ( 0 , 0 , N , M ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( not dfs ( 0 , 0 , N , M ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 2 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT matrix = [ [ 0 , 1 , 0 , 0 ] , [ 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] ] NEW_LINE print ( solve ( ) ) NEW_LINE DEDENT