HackerRank Cavity Map Problem Solution
In this Post, we will solve HackerRank Cavity Map Problem Solution.
You are given a square map as a matrix of integer strings. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side, or edge.
Find all the cavities on the map and replace their depths with the uppercase character X.
Example
grid [‘989′,’ 191′,’ 111′]
The grid is rearranged for clarity:
989
191
111
Return:
989
1X1
111
The center cell was deeper than those on its edges: [8,1,1,1]. The deep cells in the top two corners do not share an edge with the center cell, and none of the border cells is eligible.
Function Description
Complete the cavityMap function in the editor below.
cavityMap has the following parameter(s):
- string grid[n]: each string represents a row of the grid
Returns
- string{n}: the modified grid
Input Format
The first line contains an integer n, the number of rows and columns in the grid.
Each of the following n lines (rows) contains n positive digits without spaces (columns) that
represent the depth at grid[row, column].
Sample Input
STDIN Function
----- --------
4 grid[] size n = 4
1112 grid = ['1112', '1912', '1892', '1234']
1912
1892
1234
Sample Output
1112
1X12
18X2
1234
Explanation
The two cells with the depth of 9 are not on the border and are surrounded on all sides by shallower cells. Their values are replaced by X.
Cavity Map C Solution
#include<stdio.h>
int main(void)
{
int N;
scanf("%d",&N);
int mat[N][N];
int i=0,j;
for(;i<N;i++)
{
for(j=0;j<N;j++)
{
scanf("%1d",&mat[i][j]);
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if((i!=0 && i!=N-1 && j!=0 && j!=N-1) && mat[i][j]>mat[i+1][j] && mat[i][j]>mat[i][j+1] && mat[i][j]>mat[i-1][j] &&mat[i][j]>mat[i][j-1])
printf("X");
else
printf("%d",mat[i][j]);
}
printf("\n");
}
return 0;
}Cavity Map C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> grid(n);
for (string& s : grid)
cin >> s;
vector<string> grid2 = grid;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] > grid[i - 1][j] && grid[i][j] > grid[i + 1][j] && grid[i][j] > grid[i][j - 1] && grid[i][j] > grid[i][j + 1])
grid2[i][j] = 'X';
}
}
for (string& s : grid2)
cout << s << endl;
return 0;
}Cavity Map C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
var sizeOfMap = Convert.ToInt32(Console.ReadLine());
var intArray = new int[sizeOfMap][];
var outCharArray = new char[sizeOfMap][];
for (int i = 0; i < sizeOfMap; i++)
{
var input = Console.ReadLine().ToCharArray();
intArray[i] = input.Select(c => Convert.ToInt32(c.ToString())).ToArray();
outCharArray[i] = input;
}
for (int i = 1; i < sizeOfMap - 1; i++)
{
for (int j = 1; j < sizeOfMap - 1; j++)
{
var item = intArray[i][j];
var lFlag = intArray[i][j - 1] < item;
var rFlag = intArray[i][j + 1] < item;
var bFlag = intArray[i + 1][j] < item;
var tFlag = intArray[i - 1][j] < item;
var xFlag = lFlag && rFlag && bFlag && tFlag;
outCharArray[i][j] = xFlag ? 'X' : char.Parse(intArray[i][j].ToString());
}
}
for (int i = 0; i < sizeOfMap; i++)
{
Console.WriteLine(outCharArray[i]);
}
}
}Cavity Map Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'cavityMap' function below.
*
* The function is expected to return a STRING_ARRAY.
* The function accepts STRING_ARRAY grid as parameter.
*/
public static List<String> cavityMap(List<String> grid) {
// Write your code here
List<String> output = new ArrayList<>();
StringBuilder sb = new StringBuilder();
output.add(grid.get(0));
for(int i=1;i<grid.size()-1;i++){
sb.setLength(0);
sb.append(grid.get(i));
for(int j=1;j<grid.get(i).length()-1;j++){
int element = grid.get(i).charAt(j) - '0';
int side1 = grid.get(i).charAt(j-1) - '0';
int side2 = grid.get(i).charAt(j+1) - '0';
int edge1 = grid.get(i+1).charAt(j) - '0';
int edge2 = grid.get(i-1).charAt(j) - '0';
if(side1 < element && side2 < element && edge1 < element && edge2 < element){
sb.setCharAt(j, 'X');
}
}
output.add(sb.toString());
}
if(grid.size()>1){
output.add(grid.get(grid.size() - 1));
}
return output;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<String> grid = IntStream.range(0, n).mapToObj(i -> {
try {
return bufferedReader.readLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.collect(toList());
List<String> result = Result.cavityMap(grid);
bufferedWriter.write(
result.stream()
.collect(joining("\n"))
+ "\n"
);
bufferedReader.close();
bufferedWriter.close();
}
}Cavity Map JavaScript Solution
function processData(input) {
//Enter your code here
var lines=input.split('\n');
var n = parseInt( lines.shift() );
// print the resulting map
for( var y=0; y<n; y++ ) {
if( y==0 || y==n-1 ) {
// shortcut the first and last lines
process.stdout.write(lines[y] + "\n");
} else {
for( var x=0; x<n; x++ ) {
if( x==0 || x==n-1 ) {
// shortcut the first and last character in each line
process.stdout.write( lines[y].charAt(x) );
} else {
// check for a "cavity"
var me = lines[y].charAt(x);
if( me>lines[y-1].charAt(x) && me>lines[y+1].charAt(x) &&
me>lines[y].charAt(x-1) && me>lines[y].charAt(x+1) ) {
process.stdout.write('X');
} else {
process.stdout.write( lines[y].charAt(x) );
}
}
}
process.stdout.write('\n');
}
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Cavity Map Python Solution
n = int(input())
a = []
for i in range(n):
a.append(input())
s = a[0]
s += "\n"
for i in range(1, n - 1):
s += a[i][0]
for j in range(1, n - 1):
c = a[i][j]
if a[i-1][j] < c and a[i+1][j] < c and a[i][j+1] < c and a[i][j-1] < c:
s += "X"
else:
s += c
s += a[i][-1]
s += "\n"
if n > 1:
s += a[-1] + "\n"
print(s)Other Solutions
