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
Given a binary matrix mat[][] of dimensions N*M, the task is to find the minimum number of flips required from the given binary matrix such that there doesn’t exist any path from the top-left cell to the bottom-right cell consisting of only 0s.
Examples:
Input: mat[][] = {{0, 1, 0, 0}, {0, 1, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}}
Output: 1
Explanation:
Operation 1: Flipping the cell at (1, 0) modifies the given matrix to:
0 1 0 0
1 1 0 0
0 1 0 0
0 0 0 0
After the above operations, there doesn’t exists any path from the top-left cell (0, 0) to the bottom-right cell (3, 3) consisting of only 0s. Therefore, the total number of flips required is 1.Input: mat[][] = {{0, 0, 0, 0}, {0, 0, 0, 0}}
Output: 2
Approach: The given problem can be solved using the DFS Traversal on the given matrix and based on the observation that there exists only at most 2 flipping of nodes such that there doesn’t exist any path from the top-left cell to the bottom-right cell consisting of only 0s. The idea is to perform the DFS traversal from the top-left cell to the bottom-right cell to flip at most one path and print the number of successful DFS calls as the result. Follow the steps below to solve the problem:
- Initialize a function, say DFS(mat, i, j, N, M) that takes the current cell, the given matrix, and its size as the parameter and perform the following steps:
- If the current cell reaches the cell (N – 1, M – 1) then return true.
- Update the value of the cell at (i, j) to 1.
- Recursively call the DFS function in all the four directions of the current cell i.e., (i + 1, j), (i, j + 1), (i – 1, j), and (i, j – 1) if they exists.
- If the DFS Call from the cell (0, 0) returns false, then there exists no such path from the top-left to the bottom-right cell consisting of 0s. Therefore print 0 as the result and return from the function.
- Again if the DFS Call from the cell (0, 0) returns false, then there exists only one path from the top-left to the bottom-right cell consisting of 0s. Therefore print 1 as the result and return from the function.
- Otherwise, print 2 as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include "bits/stdc++.h" using namespace std; // The four direction coordinates changes // from the current cell int direction[][2] = { { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 } }; // Function that returns true if there // exists any path from the top-left to // the bottom-right cell of 0s bool dfs(vector<vector< int > >& matrix, int i, int j, int N, int M) { // If the bottom-right cell is // reached if (i == N - 1 and j == M - 1) { return true ; } // Update the cell to 1 matrix[i][j] = 1; // Traverse in all four directions for ( int k = 0; k < 4; k++) { // Find the new coordinates int newX = i + direction[k][0]; int newY = j + direction[k][1]; // If the new cell is valid if (newX >= 0 and newX < N and newY >= 0 and newY < M and matrix[newX][newY] == 0) { // Recursively call DFS if (dfs(matrix, newX, newY, N, M)) { // If path exists, then // return true return true ; } } } // Return false, if there doesn't // exists any such path return false ; } // 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 int solve(vector<vector< int > >& matrix) { int N = matrix.size(); int M = matrix[0].size(); // Case 1: If no such path exists // already if (!dfs(matrix, 0, 0, N, M)) { return 0; } // Case 2: If there exists only // one path if (!dfs(matrix, 0, 0, N, M)) { return 1; } // Case 3: If there exists two-path return 2; } // Driver Code int main() { vector<vector< int > > mat = { { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 0, 0 } }; cout << solve(mat); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // The four direction coordinates changes // from the current cell static int [][] direction = { { - 1 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 } }; // Function that returns true if there // exists any path from the top-left to // the bottom-right cell of 0s static boolean dfs( int matrix[][], int i, int j, int N, int M) { // If the bottom-right cell is // reached if (i == N - 1 && j == M - 1 ) { return true ; } // Update the cell to 1 matrix[i][j] = 1 ; // Traverse in all four directions for ( int k = 0 ; k < 4 ; k++) { // Find the new coordinates int newX = i + direction[k][ 0 ]; int newY = j + direction[k][ 1 ]; // If the new cell is valid if (newX >= 0 && newX < N && newY >= 0 && newY < M && matrix[newX][newY] == 0 ) { // Recursively call DFS if (dfs(matrix, newX, newY, N, M)) { // If path exists, then // return true return true ; } } } // Return false, if there doesn't // exists any such path return false ; } // 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 static int solve( int [][] matrix) { int N = matrix.length; int M = matrix[ 0 ].length; // Case 1: If no such path exists // already if (!dfs(matrix, 0 , 0 , N, M)) { return 0 ; } // Case 2: If there exists only // one path if (!dfs(matrix, 0 , 0 , N, M)) { return 1 ; } // Case 3: If there exists two-path return 2 ; } // Driver code 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)); } } // This code is contributed by MuskanKalra1 |
Python3
# Python3 program for the above approach # The four direction coordinates changes # from the current cell direction = [ [ - 1 , 0 ], [ 0 , 1 ], [ 0 , - 1 ],[ 1 , 0 ] ] # Function that returns true if there # exists any path from the top-left to # the bottom-right cell of 0s def dfs(i, j, N, M): global matrix # If the bottom-right cell is # reached if (i = = N - 1 and j = = M - 1 ): return True # Update the cell to 1 matrix[i][j] = 1 # Traverse in all four directions for k in range ( 4 ): # Find the new coordinates newX = i + direction[k][ 0 ] newY = j + direction[k][ 1 ] # If the new cell is valid if (newX > = 0 and newX < N and newY > = 0 and newY < M and matrix[newX][newY] = = 0 ): # Recursively call DFS if (dfs(newX, newY, N, M)): # If path exists, then # return true return True # Return false, if there doesn't # exists any such path return False # 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 def solve(): global matrix N = len (matrix) M = len (matrix[ 0 ]) # Case 1: If no such path exists # already if ( not dfs( 0 , 0 , N, M)): return 0 # Case 2: If there exists only # one path if ( not dfs( 0 , 0 , N, M)): return 1 # Case 3: If there exists two-path return 2 # Driver Code if __name__ = = '__main__' : matrix = [ [ 0 , 1 , 0 , 0 ], [ 0 , 1 , 0 , 0 ], [ 0 , 0 , 0 , 0 ] ] print (solve()) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // The four direction coordinates changes // from the current cell static int [,] direction = { { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 } }; // Function that returns true if there // exists any path from the top-left to // the bottom-right cell of 0s static bool dfs( int [,]matrix, int i, int j, int N, int M) { // If the bottom-right cell is // reached if (i == N - 1 && j == M - 1) { return true ; } // Update the cell to 1 matrix[i, j] = 1; // Traverse in all four directions for ( int k = 0; k < 4; k++) { // Find the new coordinates int newX = i + direction[k, 0]; int newY = j + direction[k, 1]; // If the new cell is valid if (newX >= 0 && newX < N && newY >= 0 && newY < M && matrix[newX, newY] == 0) { // Recursively call DFS if (dfs(matrix, newX, newY, N, M)) { // If path exists, then // return true return true ; } } } // Return false, if there doesn't // exists any such path return false ; } // 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 static int solve( int [,] matrix) { int N = matrix.GetLength(0); int M = matrix.GetLength(1); // Case 1: If no such path exists // already if (!dfs(matrix, 0, 0, N, M)) { return 0; } // Case 2: If there exists only // one path if (!dfs(matrix, 0, 0, N, M)) { return 1; } // Case 3: If there exists two-path return 2; } // Driver code public static void Main(String[] args) { int [,] mat = { { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 0, 0 } }; Console.WriteLine(solve(mat)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program for the above approach // The four direction coordinates changes // from the current cell let direction = [ [ -1, 0 ], [ 0, 1 ], [ 0, -1 ], [ 1, 0 ] ]; // Function that returns true if there // exists any path from the top-left to // the bottom-right cell of 0s function dfs(matrix, i, j, N, M) { // If the bottom-right cell is // reached if (i == N - 1 && j == M - 1) { return true ; } // Update the cell to 1 matrix[i][j] = 1; // Traverse in all four directions for (let k = 0; k < 4; k++) { // Find the new coordinates let newX = i + direction[k][0]; let newY = j + direction[k][1]; // If the new cell is valid if (newX >= 0 && newX < N && newY >= 0 && newY < M && matrix[newX][newY] == 0) { // Recursively call DFS if (dfs(matrix, newX, newY, N, M)) { // If path exists, then // return true return true ; } } } // Return false, if there doesn't // exists any such path return false ; } // 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 function solve(matrix) { let N = matrix.length; let M = matrix[0].length; // Case 1: If no such path exists // already if (!dfs(matrix, 0, 0, N, M)) { return 0; } // Case 2: If there exists only // one path if (!dfs(matrix, 0, 0, N, M)) { return 1; } // Case 3: If there exists two-path return 2; } // Driver Code let mat = [ [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ] ]; document.write(solve(mat)); </script> |
1
Time Complexity: O(N + M), as we are using loops traverse N and M times (separately).
Auxiliary Space: O(1), as we are not using any extra space.