Encuentra el número de cavidades en una array

Cuente el número de la cavidad en la array 2d, una cavidad se define como que todos los números circundantes son mayores que el número medio.
Ejemplos: 
 

Entrada: a = {{4, 5, 6}, {7, 1, 5}, {4, 5, 6}} 
Salida: 1
Entrada: a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} 
Salida: 1 
 

Fuente : Ola Interview Experience Set 13
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program find number of cavities in a matrix
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
int countCavities(int a[][MAX], int n)
{
    int A[n + 2][n + 2];
    int coun = 0;
 
    // form another matrix with one extra layer of
    // boundary elements.
    // Boundary elements will contain max value.
    for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            if ((i == 0) || (j == 0) || (i == n + 1) ||
                                         (j == n + 1))
                A[i][j] = INT_MAX;
            else
                A[i][j] = a[i - 1][j - 1];
        }
    }
 
    // Check for cavities in the modified matrix
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
 
            // check for all  directions
            if ((A[i][j] < A[i - 1][j]) && (A[i][j] < A[i + 1][j]) &&
                (A[i][j] < A[i][j - 1]) && (A[i][j] < A[i][j + 1]) &&
                (A[i][j] < A[i - 1][j - 1]) && (A[i][j] < A[i + 1][j + 1]) &&
                (A[i][j] < A[i - 1][j + 1]) && (A[i][j] < A[i + 1][j - 1]))
                coun++;
        }
    }
 
    return coun;
}
 
int main()
{
    int a[][MAX] = { { 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 } };
    int n = 3;
    cout << countCavities(a, n);
    return 0;
}

// Java program find number of cavities in a matrix
class GfG {
 
static int MAX = 100;
 
static int countCavities(int a[][], int n)
{
    int A[][] = new int[n + 2][n + 2];
    int coun = 0;
 
    // form another matrix with one extra layer of
    // boundary elements.
    // Boundary elements will contain max value.
    for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1))
                A[i][j] = Integer.MAX_VALUE;
            else
                A[i][j] = a[i - 1][j - 1];
        }
    }
 
    // Check for cavities in the modified matrix
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
 
            // check for all directions
            if ((A[i][j] < A[i - 1][j]) && (A[i][j] < A[i + 1][j]) &&
                (A[i][j] < A[i][j - 1]) && (A[i][j] < A[i][j + 1]) &&
                (A[i][j] < A[i - 1][j - 1]) && (A[i][j] < A[i + 1][j + 1]) &&
                (A[i][j] < A[i - 1][j + 1]) && (A[i][j] < A[i + 1][j - 1]))
                coun++;
        }
    }
 
    return coun;
}
 
public static void main(String[] args)
{
    int a[][] = new int[][]{{ 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 }};
    int n = 3;
System.out.println(countCavities(a, n));
}
}

# Python program find number of cavities in a matrix
import sys
MAX = 100
 
def countCavities(a, n):
 
    A = [[0 for i in range(n + 2)] for j in range(n + 2)]
    count = 0
 
    # form another matrix with one extra layer of
    # boundary elements.
    # Boundary elements will contain max value.
    for i in range(n+2):
        for j in range(n+2):
            if ((i == 0) or (j == 0) or (i == n + 1) or (j == n + 1)):
                A[i][j] = sys.maxsize
            else:
                A[i][j] = a[i - 1][j - 1]
 
    # Check for cavities in the modified matrix
    for i in range(1,n):
        for j in range(1,n):
 
            # check for all directions
            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]) and
                (A[i][j] < A[i - 1][j - 1]) and (A[i][j] < A[i + 1][j + 1]) and
                (A[i][j] < A[i - 1][j + 1]) and (A[i][j] < A[i + 1][j - 1])):
                count += 1
 
    return count
 
# driver program
a = [ [ 4, 5, 6 ], [ 7, 1, 5 ], [ 4, 5, 6 ] ]
n = 3
print(countCavities(a, n))
 
# This code is contributed by shinjanpatra

// C# program find number of cavities in a matrix
using System;
 
class GfG
{
 
    static int MAX = 100;
 
    static int countCavities(int [,]a, int n)
    {
        int [,]A = new int[n + 2, n + 2];
        int coun = 0;
 
        // form another matrix with one extra layer of
        // boundary elements.
        // Boundary elements will contain max value.
        for (int i = 0; i < n + 2; i++)
        {
            for (int j = 0; j < n + 2; j++)
            {
                if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1))
                    A[i, j] = int.MaxValue;
                else
                    A[i, j] = a[i - 1, j - 1];
            }
        }
 
        // Check for cavities in the modified matrix
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
 
                // check for all directions
                if ((A[i, j] < A[i - 1, j]) && (A[i, j] < A[i + 1, j]) &&
                    (A[i, j] < A[i, j - 1]) && (A[i, j] < A[i, j + 1]) &&
                    (A[i, j] < A[i - 1, j - 1]) && (A[i, j] < A[i + 1, j + 1]) &&
                    (A[i, j] < A[i - 1, j + 1]) && (A[i, j] < A[i + 1, j - 1]))
                    coun++;
            }
        }
        return coun;
    }
 
    public static void Main(String[] args)
    {
        int [,]a = new int[,]{{ 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 }};
        int n = 3;
        Console.WriteLine(countCavities(a, n));
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program find number of cavities
// in a matrix
function countCavities($a, $n)
{
    $A = array();
    $coun = 0;
 
    // form another matrix with one extra
    // layer of boundary elements.
    // Boundary elements will contain
    // max value.
    for ($i = 0; $i < $n + 2; $i++)
    {
        for ($j = 0; $j < $n + 2; $j++)
        {
            if (($i == 0) || ($j == 0) ||
                ($i == $n + 1) || ($j == $n + 1))
                $A[$i][$j] = 100;
            else
                $A[$i][$j] = $a[$i - 1][$j - 1];
        }
    }
 
    // Check for cavities in the modified matrix
    for ($i = 1; $i <= $n; $i++)
    {
        for ($j = 1; $j <= $n; $j++)
        {
 
            // check for all directions
            if (($A[$i][$j] < $A[$i - 1][$j]) &&
                ($A[$i][$j] < $A[$i + 1][$j]) &&
                ($A[$i][$j] < $A[$i][$j - 1]) &&
                ($A[$i][$j] < $A[$i][$j + 1]) &&
                ($A[$i][$j] < $A[$i - 1][$j - 1]) &&
                ($A[$i][$j] < $A[$i + 1][$j + 1]) &&
                ($A[$i][$j] < $A[$i - 1][$j + 1]) &&
                ($A[$i][$j] < $A[$i + 1][$j - 1]))
                $coun++;
        }
    }
 
    return $coun;
}
 
// Driver Code
$a = array(array(4, 5, 6),
           array(7, 1, 5),
           array(4, 5, 6));
$n = 3;
echo(countCavities($a, $n));
 
// This code is contributed by Code_Mech

<script>
// Javascript program find number of cavities in a matrix
 
MAX = 100;
 
function countCavities( a, n)
{
    var A = new Array(n+2).fill(0).map(() => new Array(n+2).fill(0));
    var coun = 0;
 
    // form another matrix with one extra layer of
    // boundary elements.
    // Boundary elements will contain max value.
    for (var i = 0; i < n + 2; i++) {
        for (var j = 0; j < n + 2; j++) {
            if ((i == 0) || (j == 0) || (i == n + 1) ||
                                         (j == n + 1))
                A[i][j] = Number.MAX_VALUE;
            else
                A[i][j] = a[i - 1][j - 1];
        }
    }
 
    // Check for cavities in the modified matrix
    for (var i = 1; i <= n; i++) {
        for (var j = 1; j <= n; j++) {
 
            // check for all  directions
            if ((A[i][j] < A[i - 1][j]) && (A[i][j] < A[i + 1][j]) &&
                (A[i][j] < A[i][j - 1]) && (A[i][j] < A[i][j + 1]) &&
                (A[i][j] < A[i - 1][j - 1]) && (A[i][j] < A[i + 1][j + 1]) &&
                (A[i][j] < A[i - 1][j + 1]) && (A[i][j] < A[i + 1][j - 1]))
                coun++;
        }
    }
 
    return coun;
}
 
 
 var a = [ [ 4, 5, 6 ],[ 7, 1, 5 ], [ 4, 5, 6 ] ];
 var n = 3;
 document.write( countCavities(a, n));
 
// This code is contributed by SoumikMondal
</script>

Producción: 
 

1

Optimizaciones Podemos evitar el uso de espacio adicional y condiciones adicionales siguiendo los pasos a continuación. 
1) Verifique explícitamente los elementos de las cuatro esquinas, los elementos restantes de la primera fila, la última fila, la primera columna y la última columna. 
2) Verifique los elementos restantes usando la lógica anterior.