Given a 2-D array matrix[][] of size M*N and an integer K. For each occurrence of K in the matrix[][], replace K and all the non-zero adjacent elements to its left, right, top, and bottom with 0. The program must repeat the process until all the values in the matrix become zero. The task is to find the minimum number of steps required to convert the given array matrix[][] to 0. If it’s impossible, then print -1.
Note: One step is defined as choosing an index with value K and changing its value to 0 along with it’s adjacent cells until either all the cells become 0 or index goes out of range.
Examples:
Input: M = 5, N = 5,
matrix[5][5] = {{5, 6, 0, 5, 6},
{1, 8, 8, 0, 2},
{5, 5, 5, 0, 6},
{4, 5, 5, 5, 0},
{8, 8, 8, 8, 8}},
K = 6
Output: 2
Explanation: First occurrence of 6 is found at matrix[0][1], So all the non-zero adjacent elements of left, right, top and bottom becomes zero i.e.
5 6 0 0
1 8 8 0 0 0
5 5 5 —> 0 0 0
4 5 5 5 0 0 0 0
8 8 8 8 8 0 0 0 0
So, After performing the process for the first occurrence of 6, the matrix becomes
0 0 0 5 6
0 0 0 0 2
0 0 0 0 6
0 0 0 0 0
0 0 0 0 0
Second occurrence of 6 is found at matrix[0][4], So all the non -zero adjacent elements of left, right, top and bottom becomes zero After performing the process for the second occurrence of 6, the matrix becomes
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Now, all the cell values in the matrix become zero. Hence the output is 2Input: M = 4, N = 5,
matrix[4][5] = {{5, 0, 0, 5, 6},
{1, 0, 8, 1, 0},
{0, 5, 0, 0, 6},
{4, 5, 0, 5, 2}},
K = 5
Output: 4
Approach: The idea is to traverse the matrix in all four directions left, right, top and bottom, and on finding a cell with value K, use depth-first search to change the value of all adjacent elements to 0. Follow the steps below to solve this problem:
- Initialize the variable interations_count to 0
- Iterate over the range [0, M) using the variable row and perform the following tasks:
- Iterate over the range [0, N) using the variable col and perform the following tasks:
- If matrix[row][col] equals K, then perform DFS using recursion to change all the possible element’s values to 0. Also increase the value of iterations_count by 1.
- Iterate over the range [0, N) using the variable col and perform the following tasks:
- After performing the above steps, check if any cell’s value is non-zero. If yes, then print -1, else print the value of iterations_count as the answer.
Below is the implementation of the above approach
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to implement DFS void traverse( int M, int N, vector<vector< int > >& matrix, int row, int col) { // Check the boundary conditions if (row >= 0 && row < M && col >= 0 && col < N) { if (matrix[row][col] == 0) { return ; } // Change that non-zero // adjacent element to zero matrix[row][col] = 0; // Traverse the matrix in left traverse(M, N, matrix, row, col - 1); // Traverse the matrix in Right traverse(M, N, matrix, row, col + 1); // Traverse the matrix in Top traverse(M, N, matrix, row - 1, col); //// Traverse the matrix in Bottom traverse(M, N, matrix, row + 1, col); } } void findCount( int M, int N, vector<vector< int > >& matrix, int K) { int iterations_count = 0; // Traverse the matrix and find any element // equals K, if any elements is found // increment the interations_count variable // and pass the element to the traverse function for ( int row = 0; row < M; row++) { for ( int col = 0; col < N; col++) { if (K == matrix[row][col]) { iterations_count++; traverse(M, N, matrix, row, col); } } } for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { if (matrix[i][j] != 0) { iterations_count = -1; } } } // Print the iterations count cout << iterations_count; } int main() { // Initialize the values of M and N int M = 5, N = 5; // Assigning the elements of 5*5 matrix vector<vector< int > > matrix = { { 5, 6, 0, 5, 6 }, { 1, 8, 8, 0, 2 }, { 5, 5, 5, 0, 6 }, { 4, 5, 5, 5, 0 }, { 8, 8, 8, 8, 8 } }; // Assign K as 6 int K = 6; findCount(M, N, matrix, K); return 0; } // This code is contributed by Potta Lokesh |
Java
// Java program for the above approach public class GFG { // Function to implement DFS static void traverse( int M, int N, int matrix[][], int row, int col) { // Check the boundary conditions if (row >= 0 && row < M && col >= 0 && col < N) { if (matrix[row][col] == 0 ) { return ; } // Change that non-zero // adjacent element to zero matrix[row][col] = 0 ; // Traverse the matrix in left traverse(M, N, matrix, row, col - 1 ); // Traverse the matrix in Right traverse(M, N, matrix, row, col + 1 ); // Traverse the matrix in Top traverse(M, N, matrix, row - 1 , col); //// Traverse the matrix in Bottom traverse(M, N, matrix, row + 1 , col); } } static void findCount( int M, int N, int matrix[][], int K) { int iterations_count = 0 ; // Traverse the matrix and find any element // equals K, if any elements is found // increment the interations_count variable // and pass the element to the traverse function for ( int row = 0 ; row < M; row++) { for ( int col = 0 ; col < N; col++) { if (K == matrix[row][col]) { iterations_count++; traverse(M, N, matrix, row, col); } } } for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) { if (matrix[i][j] != 0 ) { iterations_count = - 1 ; } } } // Print the iterations count System.out.print(iterations_count); } // Driver Code public static void main(String []args) { // Initialize the values of M and N int M = 5 , N = 5 ; // Assigning the elements of 5*5 matrix int matrix[][] = { { 5 , 6 , 0 , 5 , 6 }, { 1 , 8 , 8 , 0 , 2 }, { 5 , 5 , 5 , 0 , 6 }, { 4 , 5 , 5 , 5 , 0 }, { 8 , 8 , 8 , 8 , 8 } }; // Assign K as 6 int K = 6 ; findCount(M, N, matrix, K); } } // This code is contributed by AnkThon |
Python3
# python program for the above approach # Function to implement DFS def traverse(M, N, matrix, row, col): # Check the boundary conditions if (row > = 0 and row < M and col > = 0 and col < N): if (matrix[row][col] = = 0 ): return # Change that non-zero # adjacent element to zero matrix[row][col] = 0 # Traverse the matrix in left traverse(M, N, matrix, row, col - 1 ) # Traverse the matrix in Right traverse(M, N, matrix, row, col + 1 ) # Traverse the matrix in Top traverse(M, N, matrix, row - 1 , col) # Traverse the matrix in Bottom traverse(M, N, matrix, row + 1 , col) def findCount(M, N, matrix, K): iterations_count = 0 # Traverse the matrix and find any element # equals K, if any elements is found # increment the interations_count variable # and pass the element to the traverse function for row in range ( 0 , M): for col in range ( 0 , N): if (K = = matrix[row][col]): iterations_count + = 1 traverse(M, N, matrix, row, col) for i in range ( 0 , M): for j in range ( 0 , N): if (matrix[i][j] ! = 0 ): iterations_count = - 1 # Print the iterations count print (iterations_count) # Driver Code if __name__ = = "__main__" : # Initialize the values of M and N M = 5 N = 5 # Assigning the elements of 5*5 matrix matrix = [[ 5 , 6 , 0 , 5 , 6 ], [ 1 , 8 , 8 , 0 , 2 ], [ 5 , 5 , 5 , 0 , 6 ], [ 4 , 5 , 5 , 5 , 0 ], [ 8 , 8 , 8 , 8 , 8 ]] # Assign K as 6 K = 6 findCount(M, N, matrix, K) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; public class GFG { // Function to implement DFS static void traverse( int M, int N, int [,]matrix, int row, int col) { // Check the boundary conditions if (row >= 0 && row < M && col >= 0 && col < N) { if (matrix[row, col] == 0) { return ; } // Change that non-zero // adjacent element to zero matrix[row, col] = 0; // Traverse the matrix in left traverse(M, N, matrix, row, col - 1); // Traverse the matrix in Right traverse(M, N, matrix, row, col + 1); // Traverse the matrix in Top traverse(M, N, matrix, row - 1, col); //// Traverse the matrix in Bottom traverse(M, N, matrix, row + 1, col); } } static void findCount( int M, int N, int [,]matrix, int K) { int iterations_count = 0; // Traverse the matrix and find any element // equals K, if any elements is found // increment the interations_count variable // and pass the element to the traverse function for ( int row = 0; row < M; row++) { for ( int col = 0; col < N; col++) { if (K == matrix[row, col]) { iterations_count++; traverse(M, N, matrix, row, col); } } } for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) { if (matrix[i,j] != 0) { iterations_count = -1; } } } // Print the iterations count Console.WriteLine(iterations_count); } // Driver Code public static void Main(String []args) { // Initialize the values of M and N int M = 5, N = 5; // Assigning the elements of 5*5 matrix int [,]matrix = { { 5, 6, 0, 5, 6 }, { 1, 8, 8, 0, 2 }, { 5, 5, 5, 0, 6 }, { 4, 5, 5, 5, 0 }, { 8, 8, 8, 8, 8 } }; // Assign K as 6 int K = 6; findCount(M, N, matrix, K); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach // Function to implement DFS function traverse( M, N, matrix, row, col) { // Check the boundary conditions if (row >= 0 && row < M && col >= 0 && col < N) { if (matrix[row][col] == 0) { return ; } // Change that non-zero // adjacent element to zero matrix[row][col] = 0; // Traverse the matrix in left traverse(M, N, matrix, row, col - 1); // Traverse the matrix in Right traverse(M, N, matrix, row, col + 1); // Traverse the matrix in Top traverse(M, N, matrix, row - 1, col); //// Traverse the matrix in Bottom traverse(M, N, matrix, row + 1, col); } } function findCount(M, N, matrix, K) { let iterations_count = 0; // Traverse the matrix and find any element // equals K, if any elements is found // increment the interations_count variable // and pass the element to the traverse function for (let row = 0; row < M; row++) { for (let col = 0; col < N; col++) { if (K == matrix[row][col]) { iterations_count++; traverse(M, N, matrix, row, col); } } } for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) { if (matrix[i][j] != 0) { iterations_count = -1; } } } // Print the iterations count document.write(iterations_count); } // Driver Code // Initialize the values of M and N let M = 5, N = 5; // Assigning the elements of 5*5 matrix let matrix = [[ 5, 6, 0, 5, 6 ], [ 1, 8, 8, 0, 2 ], [ 5, 5, 5, 0, 6 ], [ 4, 5, 5, 5, 0 ], [ 8, 8, 8, 8, 8]]; // Assign K as 6 let K = 6; findCount(M, N, matrix, K); // This code is contributed by rohitsingh07052. </script> |
2
Time Complexity: O(M*N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!