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 | Java 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
import java . io . * ; class GFG { static int [ ] [ ] direction = { { - 1 , 0 } , { 0 , 1 } , { 0 , - 1 } , { 1 , 0 } } ; static boolean dfs ( int matrix [ ] [ ] , int i , int j , int N , int M ) { if ( i == N - 1 && 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 && newX < N && newY >= 0 && newY < M && matrix [ newX ] [ newY ] == 0 ) { if ( dfs ( matrix , newX , newY , N , M ) ) { return true ; } } } return false ; } static int solve ( int [ ] [ ] matrix ) { int N = matrix . length ; int M = matrix [ 0 ] . length ; if ( ! dfs ( matrix , 0 , 0 , N , M ) ) { return 0 ; } if ( ! dfs ( matrix , 0 , 0 , N , M ) ) { return 1 ; } return 2 ; } public static void main ( String [ ] args ) { int [ ] [ ] mat = { { 0 , 1 , 0 , 0 } , { 0 , 1 , 0 , 0 } , { 0 , 0 , 0 , 0 } } ; System . out . println ( solve ( mat ) ) ; } }