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 Bint 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 Codeint 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 approachpublic 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 Bdef 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 Codeif __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 approachusing 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> |
Output
-1
Time Complexity: O(N*M*K2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
