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++
// 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
// 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));
}
}
Python3
# 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#
// 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
// 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
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA