Check if all enemies are killed with bombs placed in a matrix
Given a Character matrix as input, the task is to check whether all the enemies are killed or not based on below conditions:
1. The matrix can contain 3 characters
X –> Denotes the War area.
B –> Denotes the bomb.
E –> Denotes the Enemies.
2. Bomb ‘B’ can blast in only horizontal and vertical directions from one end to another.
3. If all enemies are killed by the present bombs, print Yes, else print No
Examples:
Input: matrix = XXEX XBXX XEXX XXBX Output: Yes Input: matrix = XXEX XBXX XEXX XXXX Output: No
Approach: The given problem can be solved by the following approach:
- Get the character Matrix
- Traverse to find all bomb indices in the matrix
- And store the rows and column in rs and cls array.
- After all traversals, check for each enemy if there is a bomb present in that row or column or not.
- If any enemy is present in a row or column where there is no bomb, Print NO, else Print Yes.
Implementation:
C++
// C++ program to kill all enemies #include <iostream> using namespace std; // Function to find Enemies killed or not int Kill_Enemy(string s[], int row, int col) { int rs[row]={0},cls[col]={0}; for ( int i=0;i<row;i++){ for ( int j=0;j<col;j++){ if (s[i][j]== 'B' ){ rs[i]++;cls[j]++; } } } for ( int i=0;i<row;i++){ for ( int j=0;j<col;j++){ if (s[i][j]== 'E' ){ if (rs[i]==0&&cls[j]==0) return 0; } } } return 1; } // Driver Code int main( int argc, char ** argv) { // Get the input matrix string s[] = { "XXEX" , "XBXX" , "XEXX" , "XXBX" }; // Calculate Rows and columns of the string int row = sizeof (s) / sizeof (s[0]), col = s[0].length(); // Check if all enemies will be killed or not if (Kill_Enemy(s, row, col) == 1) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to kill all enemies class GFG { // Function to find Enemies killed or not static int Kill_Enemy( char [][]s, int row, int col) { int i, j, x, y; // Loop to evaluate the Bomb for (i = 0 ; i < row; i++) { for (j = 0 ; j < col; j++) { // Check if this index is a bomb if (s[i][j] == 'B' ) { // Kill all enemies // in horizontal direction for (x = 0 ; x < row; x++) { if (s[x][j] != 'B' ) s[x][j] = 'X' ; } // Kill all enemies // in vertical direction for (y = 0 ; y < col; y++) { if (s[i][y] != 'B' ) s[i][y] = 'X' ; } } } } // All bombs have been found // Check if any enemy is still present for (i = 0 ; i < row; i++) { for (j = 0 ; j < col; j++) { if (s[i][j] == 'E' ) // Since an enemy is present // Return 0 denoting No as output return 0 ; } } // Since all enemies are killed // Return 1 denoting Yes as output return 1 ; } // Driver Code public static void main(String[] args) { // Get the input matrix char [][]s = { "XXEX" .toCharArray(), "XBXX" .toCharArray(), "XEXX" .toCharArray(), "XXBX" .toCharArray() }; // Calculate Rows and columns of the String int row = s.length, col = s[ 0 ].length; // Check if all enemies will be killed or not if (Kill_Enemy(s, row, col) == 1 ) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to kill all enemies # Function to find Enemies killed or not def Kill_Enemy(s, row, col): i, j, x, y = 0 , 0 , 0 , 0 ; # Loop to evaluate the Bomb for i in range (row): for j in range (col): # Check if this index is a bomb if (s[i][j] = = 'B' ): # Kill all enemies # in horizontal direction for x in range (row): if (s[x][j] ! = 'B' ): s[x][j] = 'X' ; # Kill all enemies # in vertical direction for y in range (col): if (s[i][y] ! = 'B' ): s[i][y] = 'X' ; # All bombs have been found # Check if any enemy is still present for i in range (row): for j in range (col): if (s[i][j] = = 'E' ): # Since an enemy is present # Return 0 denoting No as output return 0 ; # Since all enemies are killed # Return 1 denoting Yes as output return 1 ; # Driver Code if __name__ = = '__main__' : # Get the input matrix s = [[ 'X' , 'X' , 'E' , 'X' ], [ 'X' , 'B' , 'X' , 'X' ], [ 'X' , 'E' , 'X' , 'X' ], [ 'X' , 'X' , 'B' , 'X' ]] # Calculate Rows and columns of the String row = len (s); col = len (s[ 0 ]); # Check if all enemies will be killed or not if (Kill_Enemy(s, row, col) = = 1 ): print ( "Yes" ); else : print ( "No" ); # This code is contributed by Rajput-Ji |
C#
// C# program to kill all enemies using System; class GFG { // Function to find Enemies killed or not static int Kill_Enemy( char [,]s, int row, int col) { int i, j, x, y; // Loop to evaluate the Bomb for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // Check if this index is a bomb if (s[i, j] == 'B' ) { // Kill all enemies // in horizontal direction for (x = 0; x < row; x++) { if (s[x, j] != 'B' ) s[x, j] = 'X' ; } // Kill all enemies // in vertical direction for (y = 0; y < col; y++) { if (s[i, y] != 'B' ) s[i, y] = 'X' ; } } } } // All bombs have been found // Check if any enemy is still present for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { if (s[i, j] == 'E' ) // Since an enemy is present // Return 0 denoting No as output return 0; } } // Since all enemies are killed // Return 1 denoting Yes as output return 1; } // Driver Code public static void Main(String[] args) { // Get the input matrix char [,]s = {{ 'X' , 'B' , 'X' , 'X' }, { 'X' , 'E' , 'X' , 'X' }, { 'X' , 'X' , 'B' , 'X' }}; // Calculate Rows and columns of the String int row = s.GetLength(0), col = s.GetLength(1); // Check if all enemies will be killed or not if (Kill_Enemy(s, row, col) == 1) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to kill all enemies // Function to find Enemies killed or not function Kill_Enemy(s, row, col) { let i, j, x, y; // Loop to evaluate the Bomb for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // Check if this index is a bomb if (s[i][j] == 'B' ) { // Kill all enemies // in horizontal direction for (x = 0; x < row; x++) { if (s[x][j] != 'B' ) s[x][j] = 'X' ; } // Kill all enemies // in vertical direction for (y = 0; y < col; y++) { if (s[i][y] != 'B' ) s[i][y] = 'X' ; } } } } // All bombs have been found // Check if any enemy is still present for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { if (s[i][j] == 'E' ) // Since an enemy is present // Return 0 denoting No as output return 0; } } // Since all enemies are killed // Return 1 denoting Yes as output return 1; } // Get the input matrix let s = [ "XXEX" .split( '' ), "XBXX" .split( '' ), "XEXX" .split( '' ), "XXBX" .split( '' ) ]; // Calculate Rows and columns of the String let row = s.length, col = s[0].length; // Check if all enemies will be killed or not if (Kill_Enemy(s, row, col) == 1) document.write( "Yes" ); else document.write( "No" ); </script> |
Output
Yes
Complexity Analysis:
- Time Complexity: O(M × N) // where M is the number of rows and N is the number of columns
- Auxiliary Space: O(1)
Contact Us