Given two binary matrices A[] and B[] of dimension N * M and a positive integer K, the task is to find the minimum number of flipping of submatrix of size K required in the matrix A[][] to convert it into the matrix B[][]. If it is not possible to convert then print “-1”.
Examples:
Input: A[][] = { { ‘1’, ‘1’, ‘1’ }, { ‘1’, ‘1’, ‘1’ }, { ‘1’, ‘1’, ‘1’ } }, B[][] = { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, K = 3
Output: 1
Explanation:
Following are the operations performed:
Operation 1: Flip the submatrix of size K from indices (0, 0) modifies the matrix A[][] to { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }.
Therefore, the minimum number of flips required is 1.Input: A[][] = { { ‘1’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, B[][] = { { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ }, { ‘0’, ‘0’, ‘0’ } }, K = 3
Output: -1
Approach: The given problem can be solved using the Greedy Approach, the idea is to traverse the given matrices A[][] and B[][] and if the corresponding cell (i, j) has a different value then flip the current submatrix of size K from indices (i, j) and count this operation of flipping. After traversing the given matrix, if there exist any indices such that submatrix of size K can’t be flipped then print “-1” as it is impossible to convert the matrix A[][] to B[][]. Otherwise, print the count of operations obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the operations // required to convert matrix A to B int minMoves(vector<vector< char >> a, vector<vector< char >> b, int K) { // Store the sizes of matrix int n = a.size(), m = a[0].size(); // Stores count of flips required int cntOperations = 0; // Traverse the given matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Check if the matrix values // are not equal if (a[i][j] != b[i][j]) { // Increment the count // of moves cntOperations++; // Check if the current // square sized exists // or not if (i + K - 1 >= n || j + K - 1 >= m) { return -1; } // Flip all the bits in this // square sized submatrix for ( int p = 0; p <= K - 1; p++) { for ( int q = 0; q <= K - 1; q++) { if (a[i + p][j + q] == '0' ) { a[i + p][j + q] = '1' ; } else { a[i + p][j + q] = '0' ; } } } } } } // Count of operations required return cntOperations; } // Driver Code int main() { vector<vector< char > > A = { { '1' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; vector<vector< char > > B = { { '0' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; int K = 3; cout << minMoves(A, B, K); return 0; } |
Java
// Java program for the above approach public class GFG { // Function to count the operations // required to convert matrix A to B static int minMoves( char a[][], char b[][], int K) { // Store the sizes of matrix int n = a.length; int m = a[ 0 ].length; // Stores count of flips required int cntOperations = 0 ; // Traverse the given matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // Check if the matrix values // are not equal if (a[i][j] != b[i][j]) { // Increment the count // of moves cntOperations++; // Check if the current // square sized exists // or not if (i + K - 1 >= n || j + K - 1 >= m) { return - 1 ; } // Flip all the bits in this // square sized submatrix for ( int p = 0 ; p <= K - 1 ; p++) { for ( int q = 0 ; q <= K - 1 ; q++) { if (a[i + p][j + q] == '0' ) { a[i + p][j + q] = '1' ; } else { a[i + p][j + q] = '0' ; } } } } } } // Count of operations required return cntOperations; } // Driver Code public static void main (String[] args) { char A[][] = { { '1' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; char B[][] = { { '0' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; int K = 3 ; System.out.println(minMoves(A, B, K)); } } // This code is contributed by AnkThon |
Python3
# python program for the above approach # Function to count the operations # required to convert matrix A to B def minMoves(a, b, K): # Store the sizes of matrix n = len (a) m = len (a[ 0 ]) # Stores count of flips required cntOperations = 0 # Traverse the given matrix for i in range ( 0 , n): for j in range ( 0 , m): # Check if the matrix values # are not equal if (a[i][j] ! = b[i][j]): # Increment the count # of moves cntOperations + = 1 # Check if the current # square sized exists # or not if (i + K - 1 > = n or j + K - 1 > = m): return - 1 # Flip all the bits in this # square sized submatrix for p in range ( 0 , K): for q in range ( 0 , K): if (a[i + p][j + q] = = '0' ): a[i + p][j + q] = '1' else : a[i + p][j + q] = '0' # Count of operations required return cntOperations # Driver Code if __name__ = = "__main__" : A = [[ '1' , '0' , '0' ], [ '0' , '0' , '0' ], [ '0' , '0' , '0' ]] B = [[ '0' , '0' , '0' ], [ '0' , '0' , '0' ], [ '0' , '0' , '0' ]] K = 3 print (minMoves(A, B, K)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to count the operations // required to convert matrix A to B static int minMoves( char [,] a, char [,] b, int K) { // Store the sizes of matrix int n = a.Length; int m = a.GetLength(0); // Stores count of flips required int cntOperations = 0; // Traverse the given matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Check if the matrix values // are not equal if (a[i, j] != b[i, j]) { // Increment the count // of moves cntOperations++; // Check if the current // square sized exists // or not if (i + K - 1 >= n || j + K - 1 >= m) { return -1; } // Flip all the bits in this // square sized submatrix for ( int p = 0; p <= K - 1; p++) { for ( int q = 0; q <= K - 1; q++) { if (a[i + p, j + q] == '0' ) { a[i + p, j + q] = '1' ; } else { a[i + p, j + q] = '0' ; } } } } } } // Count of operations required return cntOperations; } // Driver Code public static void Main() { char [,] A = new char [,]{ { '1' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; char [,] B = new char [,]{ { '0' , '0' , '0' }, { '0' , '0' , '0' }, { '0' , '0' , '0' } }; int K = 3; Console.WriteLine(minMoves(A, B, K)); } } // This code is contributed by Saurabh. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count the operations // required to convert matrix A to B function minMoves(a, b, K) { // Store the sizes of matrix let n = a.length, m = a[0].length; // Stores count of flips required let cntOperations = 0; // Traverse the given matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // Check if the matrix values // are not equal if (a[i][j] != b[i][j]) { // Increment the count // of moves cntOperations++; // Check if the current // square sized exists // or not if (i + K - 1 >= n || j + K - 1 >= m) { return -1; } // Flip all the bits in this // square sized submatrix for (let p = 0; p <= K - 1; p++) { for (let q = 0; q <= K - 1; q++) { if (a[i + p][j + q] == '0' ) { a[i + p][j + q] = '1' ; } else { a[i + p][j + q] = '0' ; } } } } } } // Count of operations required return cntOperations; } // Driver Code let A = [[ '1' , '0' , '0' ], [ '0' , '0' , '0' ], [ '0' , '0' , '0' ]]; let B = [[ '0' , '0' , '0' ], [ '0' , '0' , '0' ], [ '0' , '0' , '0' ]]; let K = 3; document.write(minMoves(A, B, K)); // This code is contributed by Potta Lokesh </script> |
-1
Time Complexity: O(N*M*K2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!