Given a matrix letter[][] of size N * M, composed of ‘#’ and ‘*’ and another matrix stamp[][] of size X * Y containing only ‘$’. The task is to find if all the ‘*’ of the larger one can be replaced by ‘$’ by superimposing the stamp matrix on the letter matrix.
Note: In a superimpose operation only a area having all the characters as ‘*’ or ‘$’ can be considered.
Examples:
Input: N = 3, M =5, X = 2, Y=2
Letter Matrix:
#****
#****
#****
Stamp Matrix:
$$
$$
Output: Possible
Explanation:
1st Step: Superimpose letter matrix from (0,1) to (1,2) , So, letter will look like ( Remember the place where ‘#’ is placed can’t be imposed)
#$$**
#$$**
#****
2nd Step: Superimpose letter matrix from (0,3) to (1,4), Letter becomes
#$$$$
#$$$$
#****
3rd Step: Since superimpose over ‘$’ is also allowed, do overlapping. Hence stamping next from (1,1) to (2,3)
#$$$$
#$$$$
#$$**
Final step: Again do overlapping, and stamp from (1,3) to (3,4)
#$$$$
#$$$$
#$$$$
Input: N = 3, M =5, X = 2, Y=2
Letter Matrix:
#**#*
#****
#****
Stamp Matrix:
$$
$$
Output: Impossible
Explanation: The ‘#’ at (0,3) cannot be superimposed.
Approach: The problem can be solved by checking the number of ‘*’ characters between two ‘#’ or at the end and starting of a row. If any of these counts are less than the row length of stamp matrix then solution is not possible, Same is applicable for columns also. Follow the steps mentioned below to implement the approach:
- Loop over complete larger matrix row wise
- For each row, count the number of consecutive ‘*’ at the beginning or before end of row or between two ‘#’. If this count is smaller than stamp matrix row length then its impossible and return impossible as answer.
- Check the whole letter matrix in this manner.
- Apply the same process for the columns also.
- If the letter matrix can be superimposed return true. Otherwise, return false.
Below is the implementation of the above approach
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to check if superimpose // is possible or not bool solution( int n, int m, int x, int y, vector<string>& letter) { // Looping over rows for ( int i = 0; i < n; i++) { // Initializing a length variable // for counting the number of * int len = 0; for ( int j = 0; j < m; j++) { // If character encountered // is *, then we // increment the length if (letter[i][j] == '*' ) len++; // If its not then there are // two cases else { // 1st case is length is // smaller than number of // rows in stamp matrix, // that would be impossible // to stamp so return false if (len != 0 && len < x) return false ; // 2nd case is if its // possible, reset len else len = 0; } } } // Do similarly for columns // Looping over columns for ( int i = 0; i < m; i++) { // Initializing length variable int len = 0; for ( int j = 0; j < n; j++) { // If encountered character // is *, increment length if (letter[j][i] == '*' ) len++; else { // If its not possible // return false if (len != 0 && len < y) return false ; // Otherwise reset len else len = 0; } } } return true ; } // Driver code int main() { int n = 3, x = 2, y = 2; vector<string> letter = { "#***" , "#***" , "#***" }; int m = letter[0].size(); /* Stamp Matrix: $$ $$ A 2*2 matrix ( x*y) */ if (solution(n, m, x, y, letter)) cout << "Possible\n" ; else cout << "Impossible\n" ; // 2nd case vector<string> letter2 = { "#***" , "#*#*" , "#***" }; m = letter2[0].size(); if (solution(n, m, x, y, letter2)) cout << "Possible\n" ; else cout << "Impossible\n" ; return 0; } // This code is contributed by rakeshsahni |
Java
// Java code to implement the above approach import java.util.*; class GFG { // Function to check if superimpose // is possible or not public static boolean solution( int n, int m, int x, int y, String[] letter) { // Looping over rows for ( int i = 0 ; i < n; i++) { // Initializing a length variable // for counting the number of * int len = 0 ; for ( int j = 0 ; j < m; j++) { // If character encountered // is *, then we // increment the length if (letter[i].charAt(j) == '*' ) len++; // If its not then there are // two cases else { // 1st case is length is // smaller than number of // rows in stamp matrix, // that would be impossible // to stamp so return false if (len != 0 && len < x) return false ; // 2nd case is if its // possible, reset len else len = 0 ; } } } // Do similarly for columns // Looping over columns for ( int i = 0 ; i < m; i++) { // Initializing length variable int len = 0 ; for ( int j = 0 ; j < n; j++) { // If encountered character // is *, increment length if (letter[j].charAt(i) == '*' ) len++; else { // If its not possible // return false if (len != 0 && len < y) return false ; // Otherwise reset len else len = 0 ; } } } return true ; } // Driver code public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = 3 , x = 2 , y = 2 ; String[] letter = { "#***" , "#***" , "#***" }; int m = letter[ 0 ].length(); /* Stamp Matrix: $$ $$ A 2*2 matrix ( x*y) */ if (solution(n, m, x, y, letter)) System.out.println( "Possible" ); else System.out.println( "Impossible" ); // 2nd case String[] letter2 = { "#***" , "#*#*" , "#***" }; m = letter2[ 0 ].length(); if (solution(n, m, x, y, letter2)) System.out.println( "Possible" ); else System.out.println( "Impossible" ); } } |
Python3
# Python code to implement the above approach # Function to check if superimpose # is possible or not def solution(n, m, x, y, letter): # Looping over rows for i in range (n): # Initializing a length variable # for counting the number of * len = 0 for j in range (m): # If character encountered # is *, then we # increment the length if (letter[i][j] = = '*' ): len + = 1 # If its not then there are # two cases else : # 1st case is length is # smaller than number of # rows in stamp matrix, # that would be impossible # to stamp so return false if ( len ! = 0 and len < x): return False # 2nd case is if its # possible, reset len else : len = 0 # Do similarly for columns # Looping over columns for i in range (m): # Initializing length variable len = 0 for j in range (n): # If encountered character # is *, increment length if (letter[j][i] = = '*' ): len + = 1 else : # If its not possible # return false if ( len ! = 0 and len < y): return False # Otherwise reset len else : len = 0 return True # Driver code n = 3 x = 2 y = 2 letter = [ "#***" , "#***" , "#***" ] m = len (letter[ 0 ]) ''' Stamp Matrix: $$ $$ A 2*2 matrix ( x*y) ''' if (solution(n, m, x, y, letter)): print ( "Possible" ) else : print ( "Impossible" ) # 2nd case letter2 = [ "#***" , "#*#*" , "#***" ] m = len (letter2[ 0 ]) if (solution(n, m, x, y, letter2)): print ( "Possible" ) else : print ( "Impossible" ) # This code is contributed by Shubham Singh |
C#
// C# code to implement the above approach using System; class GFG{ // Function to check if superimpose // is possible or not public static bool solution( int n, int m, int x, int y, string [] letter) { // Looping over rows for ( int i = 0; i < n; i++) { // Initializing a length variable // for counting the number of * int len = 0; for ( int j = 0; j < m; j++) { // If character encountered // is *, then we // increment the length if (letter[i][j] == '*' ) len++; // If its not then there are // two cases else { // 1st case is length is // smaller than number of // rows in stamp matrix, // that would be impossible // to stamp so return false if (len != 0 && len < x) return false ; // 2nd case is if its // possible, reset len else len = 0; } } } // Do similarly for columns // Looping over columns for ( int i = 0; i < m; i++) { // Initializing length variable int len = 0; for ( int j = 0; j < n; j++) { // If encountered character // is *, increment length if (letter[j][i] == '*' ) len++; else { // If its not possible // return false if (len != 0 && len < y) return false ; // Otherwise reset len else len = 0; } } } return true ; } // Driver code public static void Main( string [] args) { int n = 3, x = 2, y = 2; string [] letter = { "#***" , "#***" , "#***" }; int m = letter.GetLength(0); /* Stamp Matrix: $$ $$ A 2*2 matrix ( x*y) */ if (solution(n, m, x, y, letter)) Console.WriteLine( "Possible" ); else Console.WriteLine( "Impossible" ); // 2nd case String[] letter2 = { "#***" , "#*#*" , "#***" }; m = letter2.GetLength(0); if (solution(n, m, x, y, letter2)) Console.WriteLine( "Possible" ); else Console.WriteLine( "Impossible" ); } } // This code is contributed by ukasp |
Javascript
<script> // Javascript code for the above approach // Function to check if superimpose // is possible or not function solution(n, m, x, y,letter) { // Looping over rows for ( var i = 0; i < n; i++) { // Initializing a length variable // for counting the number of * var len = 0; for ( var j = 0; j < m; j++) { // If character encountered // is *, then we // increment the length if (letter[i][j] == '*' ) len++; // If its not then there are // two cases else { // 1st case is length is // smaller than number of // rows in stamp matrix, // that would be impossible // to stamp so return false if (len != 0 && len < x) return false ; // 2nd case is if its // possible, reset len else len = 0; } } } // Do similarly for columns // Looping over columns for ( var i = 0; i < m; i++) { // Initializing length variable var len = 0; for ( var j = 0; j < n; j++) { // If encountered character // is *, increment length if (letter[j][i] == '*' ) len++; else { // If its not possible // return false if (len != 0 && len < y) return false ; // Otherwise reset len else len = 0; } } } return true ; } // Driver code var n = 3, x = 2, y = 2; var letter = [ "#***" , "#***" , "#***" ]; var m = letter[0].length; /* Stamp Matrix: $$ $$ A 2*2 matrix ( x*y) */ if (solution(n, m, x, y, letter)) document.write( "Possible" + "<br>" ); else document.write( "Impossible" + "<br>" ); // 2nd case var letter2 = [ "#***" , "#*#*" , "#***" ]; m = letter2[0].length; if (solution(n, m, x, y, letter2)) document.write( "Possible" + "<br>" ); else document.write( "Impossible" + "<br>" ); // This code is contributed by Shubham Singh </script> |
Impossible
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!