HackerRank Cavity Map Solution

ByBrokenprogrammers

Dec 12, 2022

Hello Programmers, In this post, you will know how to solve the HackerRank Cavity Map Solution. This problem is a part of the HackerRank Algorithms Series.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank Cavity Map 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[rowcolumn].

Constraints

• 1 <= n <= 100

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.

HackerRank Cavity Map Solution

Cavity Map Solution in C

```#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define clr(ar) memset(ar, 0, sizeof(ar))
int n;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char str[1010][1010], res[1010][1010];
int main(){
int i, j, k;
while (scanf("%d", &n) != EOF){
for (i = 0; i < n; i++) scanf("%s", str[i]);
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
res[i][j] = str[i][j];
if (i == 0 || j == 0 || i == (n - 1) || j == (n - 1)) continue;
int max = -1;
for (k = 0; k < 4; k++){
int x = i + dx[k];
int y = j + dy[k];
if (str[x][y] > max) max = str[x][y];
}
if (max < str[i][j]) res[i][j] = 'X';
}
res[i][n] = 0;
}
for (i = 0; i < n; i++) puts(res[i]);
}
return 0;
}```

Cavity Map Solution in Cpp

```#include <bits/stdc++.h>
using namespace std;
int N;
char grid[101][101];
char grid2[101][101];
int main()
{
scanf("%d\n", &N);
for(int i=0; i<N; i++)
gets(grid[i]);
memcpy(grid2, grid, sizeof grid2);
for(int i=1; i<N-1; i++)
for(int j=1; j<N-1; j++)
if(grid[i][j]>grid[i+1][j])
if(grid[i][j]>grid[i-1][j])
if(grid[i][j]>grid[i][j+1])
if(grid[i][j]>grid[i][j-1])
grid2[i][j]='X';
for(int i=0; i<N; i++)
puts(grid2[i]);
return 0;
}```

Cavity Map Solution in Java

```import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
public class Solution {
public static void main(String[] args) throws Exception {
BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
char a[][] = new char[n][];
for (int i = 0; i < n; i++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == 0 || i == n - 1 || j == 0 || j == n - 1) continue;
boolean flag = true;
if (a[i - 1][j] >= a[i][j]) flag = false;
if (a[i + 1][j] >= a[i][j]) flag = false;
if (a[i][j - 1] >= a[i][j]) flag = false;
if (a[i][j + 1] >= a[i][j]) flag = false;
if (flag) a[i][j] = 'X';
}
for (int i = 0; i < n; i++)
cout.write(String.valueOf(a[i]) + "\n");
cin.close();
cout.close();
}
static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
final U _1;
final V _2;
private Pair(U key, V val) {
this._1 = key;
this._2 = val;
}
public static <U extends Comparable<U>, V extends Comparable<V>> Pair<U, V> instanceOf(U _1, V _2) {
return new Pair<U, V>(_1, _2);
}
@Override
public String toString() {
return _1 + " " + _2;
}
@Override
public int hashCode() {
int res = 17;
res = res * 31 + _1.hashCode();
res = res * 31 + _2.hashCode();
return res;
}
@Override
public int compareTo(Pair<U, V> that) {
int res = this._1.compareTo(that._1);
if (res < 0 || res > 0) return res;
else return this._2.compareTo(that._2);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof Pair)) return false;
Pair<?, ?> that = (Pair<?, ?>) obj;
return _1.equals(that._1) && _2.equals(that._2);
}
}
}```

Cavity Map Solution in Python

```import sys
m = []
for ix in range(n):
if l[-1] == '\n':
l = l[:-1]
m.append([int(c) for c in l])
m2 = [[c for c in l] for l in m]
ds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for x in range(1, n - 1):
for y in range(1, n - 1):
v = m[x][y]
if all(map(lambda z: m[x + z[0]][y + z[1]] < v, ds)):
m2[x][y] = 'X'
for l in m2:
print ''.join(map(str, l))
```

Cavity Map Solution using JavaScript

```'use strict';
function processData(input) {
var parse_fun = function (s) { return parseInt(s, 10); };
var lines = input.split('\n');
var N = parse_fun(lines.shift().trim());
var map = [];
for (var i = 0; i < N; i++) {
var row = lines[i].trim().split('').splice(0, N).map(parse_fun);
map[i] = row;
}
for (var i = 1; i < N - 1; i++) {
for (var j = 1; j < N - 1; j++) {
var c = map[i][j];
var c1 = map[i + 1][j];
var c2 = map[i - 1][j];
var c3 = map[i][j + 1];
var c4 = map[i][j - 1];
if (c == 'X' || c1 == 'X' || c2 == 'X' || c3 == 'X' || c4 == 'X') { continue; }
if (c > c1 && c > c2 && c > c3 && c > c4) {
map[i][j] = 'X';
}
}}
for (var i = 0; i < N; i++) {
console.log(map[i].join(''));
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) { _input += input; });
process.stdin.on("end", function () { processData(_input); });```

Cavity Map Solution in Scala

```object Solution {
def main(args: Array[String]) {
val arr = Array.fill(N)(readLine.toCharArray().map(_.toInt - 48))
for (i <- 0 to N - 1) {
for (j <- 0 to N - 1) {
if (i > 0 && i < N - 1 && j > 0 && j < N - 1) {
if (arr(i)(j) > arr(i - 1)(j) && arr(i)(j) > arr(i + 1)(j) && arr(i)(j) > arr(i)(j - 1) && arr(i)(j) > arr(i)(j + 1)) {
print("X")
} else {
print(arr(i)(j))
}
} else {
print(arr(i)(j))
}
}
println
}
}
}```

Cavity Map Solution in Pascal

```var n,i,j:longint;
a:array [1..100,1..100] of char;
begin
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
end;
for i:=2 to n-1 do
for j:=2 to n-1 do
begin
if (a[i,j]>a[i-1,j])and
(a[i,j]>a[i+1,j])and
(a[i,j]>a[i,j-1])and
(a[i,j]>a[i,j+1])then a[i,j]:='X';
end;
for i:=1 to n do
begin
for j:=1 to n do write(a[i,j]);
writeln;
end;
end.
```

Disclaimer: This problem (Cavity Map) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.