Given a matrix mat[][] containing the characters [1 – 9], P and * where P is a person and * is an empty space. An integer in the current cell denotes a bomb that can destroy an object within a radius equal to the value of the cell. The task is to count and print the number of persons that will survive the blast.
Examples:
Input:
mat[] = { "P***",
"****",
"2**P",
"****" }
Output: 1
Only the person in the third row
will survive. Note that the person
in the first row is within the
radius of the bomb.
Input:
mat[] = { "2***P*",
"P*****",
"******",
"**1***",
"******",
"*****P" }
Output: 2
The persons in the first and last
row survive.
Approach:
Traverse the matrix character by character, if the current character is a digit (1 – 9) then change all the surrounding elements within the radius to * (in all eight directions) indicating that no one survived within that radius. After all the elements of the matrix have been traversed, count the number of cells indicating a person i.e. mat[i][j] = ‘P’. Print the count in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the count of// the people that survivedint countSurvivors(string mat[], int row, int col){ int i, j, count = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // If current cell is a bomb if (mat[i][j] > '0' && mat[i][j] <= '9') { int radius = mat[i][j] - '0'; // Coordinates of the sub-matrix // that will be affected by the blast int iMin = max(i - radius, 0); int iMax = min(i + radius, row - 1); int jMin = max(j - radius, 0); int jMax = min(j + radius, col - 1); for (int k = iMin; k <= iMax; k++) for (int l = jMin; l <= jMax; l++) // Set the current cell to // empty space without a person mat[k][l] = '*'; } } } // Count the remaining persons for (i = 0; i < row; i++) for (j = 0; j < col; j++) if (mat[i][j] == 'P') count++; return count;}// Driver Codeint main(){ // Input matrix string mat[] = { "P***", "****", "2**P", "****" }; // Rows and columns of the matrix int row = sizeof(mat) / sizeof(mat[0]); int col = mat[0].length(); // Total people survived cout << countSurvivors(mat, row, col);} |
Java
// Java implementation of the approach class GFG{// Function to return the count of // the people that survived static int countSurvivors(String mat[], int row, int col) { int i, j, count = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // If current cell is a bomb if (mat[i].charAt(j) > '0' && mat[i].charAt(j) <= '9') { int radius = mat[i].charAt(j) - '0'; // Coordinates of the sub-matrix // that will be affected by the blast int iMin = Math.max(i - radius, 0); int iMax = Math.min(i + radius, row - 1); int jMin = Math.max(j - radius, 0); int jMax = Math.min(j + radius, col - 1); for (int k = iMin; k <= iMax; k++) { // convert string nto character array char C [] = mat[k].toCharArray(); for (int l = jMin; l <= jMax; l++) { // Set the current cell to // empty space without a person C [l] = '*' ; } // convert character array back into the string String s = new String(C) ; mat[k] = s ; } } } } // Count the remaining persons for (i = 0; i < row; i++) for (j = 0; j < col; j++) if (mat[i].charAt(j) == 'P') count++; return count; } // Driver Code public static void main(String []args) { // Input matrix String mat[] = { "P***", "****", "2**P", "****" }; // Rows and columns of the matrix int row = mat.length ; int col = mat[0].length(); // Total people survived System.out.println(countSurvivors(mat, row, col)); } }// This code is contributed by Ryuga |
Python3
# Python3 implementation of the approachimport math as mt# Function to return the count of# the people that surviveddef countSurvivors(mat, row, col): i, j, count = 0, 0, 0 for i in range(row): for j in range(col): # If current cell is a bomb if (mat[i][j] > '0' and mat[i][j] <= '9'): radius = ord(mat[i][j]) - ord('0') # Coordinates of the sub-matrix # that will be affected by the blast iMin = max(i - radius, 0) iMax = min(i + radius, row - 1) jMin = max(j - radius, 0) jMax = min(j + radius, col - 1) for k in range(iMin, iMax + 1): for l in range(jMin, jMax + 1): # Set the current cell to # empty space without a person mat[k][l] = '*' # Count the remaining persons for i in range(row): for j in range(col): if (mat[i][j] == 'P'): count += 1 return count# Driver Code# Input matrixmat = [["P", "*", "*", "*"], ["*", "*", "*", "*"], ["2", "*", "*", "P"], ["*", "*", "*", "*"]]# Rows and columns of the matrixrow = len(mat)col = len(mat[0])# Total people survivedprint(countSurvivors(mat, row, col))# This code is contributed by# Mohit Kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{// Function to return the count of // the people that survived static int countSurvivors(String []mat, int row, int col) { int i, j, count = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // If current cell is a bomb if (mat[i][j] > '0' && mat[i][j] <= '9') { int radius = mat[i][j] - '0'; // Coordinates of the sub-matrix // that will be affected by the blast int iMin = Math.Max(i - radius, 0); int iMax = Math.Min(i + radius, row - 1); int jMin = Math.Max(j - radius, 0); int jMax = Math.Min(j + radius, col - 1); for (int k = iMin; k <= iMax; k++) { // convert string nto character array char []C = mat[k].ToCharArray(); for (int l = jMin; l <= jMax; l++) { // Set the current cell to // empty space without a person C [l] = '*'; } // convert character array back into the string String s = new String(C); mat[k] = s; } } } } // Count the remaining persons for (i = 0; i < row; i++) for (j = 0; j < col; j++) if (mat[i][j] == 'P') count++; return count; } // Driver Code public static void Main(String []args){ // Input matrix String []mat = { "P***", "****", "2**P", "****" }; // Rows and columns of the matrix int row = mat.Length ; int col = mat[0].Length; // Total people survived Console.WriteLine(countSurvivors(mat, row, col)); } }// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach // Function to return the count of // the people that survived function countSurvivors(mat, row, col) { let i, j, count = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // If current cell is a bomb if (mat[i][j].charCodeAt() > '0'.charCodeAt() && mat[i][j].charCodeAt() <= '9'.charCodeAt()) { let radius = mat[i][j].charCodeAt() - '0'.charCodeAt(); // Coordinates of the sub-matrix // that will be affected by the blast let iMin = Math.max(i - radius, 0); let iMax = Math.min(i + radius, row - 1); let jMin = Math.max(j - radius, 0); let jMax = Math.min(j + radius, col - 1); for (let k = iMin; k <= iMax; k++) { // convert string nto character array let C = mat[k].split(''); for (let l = jMin; l <= jMax; l++) { // Set the current cell to // empty space without a person C[l] = '*' ; } // convert character array // back into the string let s = C.join(""); mat[k] = s ; } } } } // Count the remaining persons for (i = 0; i < row; i++) for (j = 0; j < col; j++) if (mat[i][j] == 'P') count++; return count; } // Input matrix let mat = [ "P***", "****", "2**P", "****" ]; // Rows and columns of the matrix let row = mat.length; let col = mat[0].length; // Total people survived document.write(countSurvivors(mat, row, col)); </script> |
Output
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!
