Dada una array 2-D y un número entero ‘K’, la tarea es predecir la array después de ‘K’ iteraciones dadas de la siguiente manera:
- Un elemento 1 en la array actual sigue siendo 1 en la siguiente iteración solo si está rodeado por un número de 1, donde 0 <= range1a <= A <= range1b.
- Un elemento 0 en la array actual se convierte en 1 en la siguiente iteración solo si está rodeado por B números de 1, donde 0 <= range0a <= B <= range0b.
Entendamos esto con un ejemplo:
Restricciones:
1 <= K <= 100000
0 <= range1a, range1b, range0a, range0b <= 8
- En la imagen de arriba para la celda (0, 0), la celda era ‘0’ en la primera iteración pero, dado que estaba rodeada solo por una celda adyacente que contenía ‘1’, que no se encuentra dentro del rango [rango0a, rango0b] . Por lo que seguirá siendo ‘0’.
- Para la segunda iteración, la celda (0, 0) era 0, pero esta vez está rodeada por dos celdas que contienen ‘1’, y dos caen dentro del rango [rango0a, rango0b]. Por lo tanto, se convierte en ‘1’ en la siguiente (2ª) iteración.
Ejemplos:
Entrada: range1a = 2
range1b = 2
range0a = 2
range0b = 3
K = 1
Salida:
0 1 1 0
0 1 1 1
1 0 0 1
0 0 1 0
Entrada: range1a = 2
range1b = 2
range0a = 2
range0b = 3
K = 2
Salida:
1 0 0 1
1 0
0 0 0 0 0
0 0 1 0 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Dimension of Array
#define N 4
void predictMatrix(int arr[N][N],
int range1a,
int range1b,
int range0a,
int range0b,
int K,
int b[N][N])
{
// Count of 1s
int c = 0;
while (K--) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
c = 0;
// Counting all neighbouring 1s
if (i > 0 && arr[i - 1][j] == 1)
c++;
if (j > 0 && arr[i][j - 1] == 1)
c++;
if (i > 0 && j > 0
&& arr[i - 1][j - 1] == 1)
c++;
if (i < N - 1 && arr[i + 1][j] == 1)
c++;
if (j < N - 1 && arr[i][j + 1] == 1)
c++;
if (i < N - 1 && j < N - 1
&& arr[i + 1][j + 1] == 1)
c++;
if (i < N - 1 && j > 0
&& arr[i + 1][j - 1] == 1)
c++;
if (i > 0 && j < N - 1
&& arr[i - 1][j + 1] == 1)
c++;
// Comparing the number of
// neighbouring 1s with
// given ranges
if (arr[i][j] == 1) {
if (c >= range1a && c <= range1b)
b[i][j] = 1;
else
b[i][j] = 0;
}
if (arr[i][j] == 0) {
if (c >= range0a && c <= range0b)
b[i][j] = 1;
else
b[i][j] = 0;
}
}
}
// Copying changes to
// the main matrix
for (int k = 0; k < N; k++)
for (int m = 0; m < N; m++)
arr[k][m] = b[k][m];
}
}
// Driver code
int main()
{
int arr[N][N] = { 0, 0, 0, 0,
0, 1, 1, 0,
0, 0, 1, 0,
0, 1, 0, 1 };
int range1a = 2, range1b = 2;
int range0a = 2, range0b = 3;
int K = 3, b[N][N] = { 0 };
// Function call to calculate
// the resultant matrix
// after 'K' iterations.
predictMatrix(arr, range1a, range1b,
range0a, range0b, K, b);
// Printing Result
for (int i = 0; i < N; i++) {
cout << endl;
for (int j = 0; j < N; j++)
cout << b[i][j] << " ";
}
return 0;
}
Java
// Java implementation of the approach
public class GFG{
// Dimension of Array
final static int N = 4 ;
static void predictMatrix(int arr[][],
int range1a,
int range1b,
int range0a,
int range0b,
int K,
int b[][])
{
// Count of 1s
int c = 0;
while (K != 0) {
K--;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
c = 0;
// Counting all neighbouring 1s
if (i > 0 && arr[i - 1][j] == 1)
c++;
if (j > 0 && arr[i][j - 1] == 1)
c++;
if (i > 0 && j > 0
&& arr[i - 1][j - 1] == 1)
c++;
if (i < N - 1 && arr[i + 1][j] == 1)
c++;
if (j < N - 1 && arr[i][j + 1] == 1)
c++;
if (i < N - 1 && j < N - 1
&& arr[i + 1][j + 1] == 1)
c++;
if (i < N - 1 && j > 0
&& arr[i + 1][j - 1] == 1)
c++;
if (i > 0 && j < N - 1
&& arr[i - 1][j + 1] == 1)
c++;
// Comparing the number of
// neighbouring 1s with
// given ranges
if (arr[i][j] == 1) {
if (c >= range1a && c <= range1b)
b[i][j] = 1;
else
b[i][j] = 0;
}
if (arr[i][j] == 0) {
if (c >= range0a && c <= range0b)
b[i][j] = 1;
else
b[i][j] = 0;
}
}
}
// Copying changes to
// the main matrix
for (int k = 0; k < N; k++)
for (int m = 0; m < N; m++)
arr[k][m] = b[k][m];
}
}
// Driver code
public static void main(String []args)
{
int arr[][] = { {0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 0},
{0, 1, 0, 1 } };
int range1a = 2, range1b = 2;
int range0a = 2, range0b = 3;
int K = 3;
int b[][] = new int[N][N] ;
// Function call to calculate
// the resultant matrix
// after 'K' iterations.
predictMatrix(arr, range1a, range1b,
range0a, range0b, K, b);
// Printing Result
for (int i = 0; i < N; i++) {
System.out.println();
for (int j = 0; j < N; j++)
System.out.print(b[i][j]+ " ");
}
}
// This Code is contributed by Ryuga
}
Python 3
# Python3 implementation of the approach # Dimension of Array N = 4 def predictMatrix(arr, range1a, range1b, range0a, range0b, K, b): # Count of 1s c = 0 while (K): for i in range(N) : for j in range(N): c = 0 # Counting all neighbouring 1s if (i > 0 and arr[i - 1][j] == 1): c += 1 if (j > 0 and arr[i][j - 1] == 1): c += 1 if (i > 0 and j > 0 and arr[i - 1][j - 1] == 1): c += 1 if (i < N - 1 and arr[i + 1][j] == 1): c += 1 if (j < N - 1 and arr[i][j + 1] == 1): c += 1 if (i < N - 1 and j < N - 1 and arr[i + 1][j + 1] == 1): c += 1 if (i < N - 1 and j > 0 and arr[i + 1][j - 1] == 1): c += 1 if (i > 0 and j < N - 1 and arr[i - 1][j + 1] == 1): c += 1 # Comparing the number of neighbouring # 1s with given ranges if (arr[i][j] == 1) : if (c >= range1a and c <= range1b): b[i][j] = 1 else: b[i][j] = 0 if (arr[i][j] == 0): if (c >= range0a and c <= range0b): b[i][j] = 1 else: b[i][j] = 0 K -= 1 # Copying changes to the main matrix for k in range(N): for m in range( N): arr[k][m] = b[k][m] # Driver code if __name__ == "__main__": arr = [[0, 0, 0, 0], [0, 1, 1, 0], [0, 0, 1, 0], [0, 1, 0, 1]] range1a = 2 range1b = 2 range0a = 2 range0b = 3 K = 3 b = [[0 for x in range(N)] for y in range(N)] # Function call to calculate # the resultant matrix # after 'K' iterations. predictMatrix(arr, range1a, range1b, range0a, range0b, K, b) # Printing Result for i in range( N): print() for j in range(N): print(b[i][j], end = " ") # This code is contributed # by ChitraNayal
C#
// C# implementation of the approach
using System;
class GFG
{
// Dimension of Array
readonly static int N = 4 ;
static void predictMatrix(int [,]arr, int range1a,
int range1b, int range0a,
int range0b, int K, int [,]b)
{
// Count of 1s
int c = 0;
while (K != 0)
{
K--;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
c = 0;
// Counting all neighbouring 1s
if (i > 0 && arr[i - 1, j] == 1)
c++;
if (j > 0 && arr[i, j - 1] == 1)
c++;
if (i > 0 && j > 0
&& arr[i - 1, j - 1] == 1)
c++;
if (i < N - 1 && arr[i + 1, j] == 1)
c++;
if (j < N - 1 && arr[i, j + 1] == 1)
c++;
if (i < N - 1 && j < N - 1 &&
arr[i + 1, j + 1] == 1)
c++;
if (i < N - 1 && j > 0 &&
arr[i + 1, j - 1] == 1)
c++;
if (i > 0 && j < N - 1 &&
arr[i - 1, j + 1] == 1)
c++;
// Comparing the number of
// neighbouring 1s with
// given ranges
if (arr[i,j] == 1)
{
if (c >= range1a && c <= range1b)
b[i, j] = 1;
else
b[i, j] = 0;
}
if (arr[i,j] == 0)
{
if (c >= range0a && c <= range0b)
b[i, j] = 1;
else
b[i, j] = 0;
}
}
}
// Copying changes to the main matrix
for (int k = 0; k < N; k++)
for (int m = 0; m < N; m++)
arr[k, m] = b[k, m];
}
}
// Driver code
public static void Main()
{
int [,]arr = { {0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 0},
{0, 1, 0, 1 } };
int range1a = 2, range1b = 2;
int range0a = 2, range0b = 3;
int K = 3;
int [,]b = new int[N, N];
// Function call to calculate
// the resultant matrix
// after 'K' iterations.
predictMatrix(arr, range1a, range1b,
range0a, range0b, K, b);
// Printing Result
for (int i = 0; i < N; i++)
{
Console.WriteLine();
for (int j = 0; j < N; j++)
Console.Write(b[i, j] + " ");
}
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
// Dimension of Array
#define N 4
function predictMatrix($arr, $range1a, $range1b,
$range0a, $range0b, $K, $b)
{
$N = 4;
// Count of 1s
$c = 0;
while ($K--)
{
for ($i = 0; $i < $N; $i++)
{
for ($j = 0; $j < $N; $j++)
{
$c = 0;
// Counting all neighbouring 1s
if ($i > 0 && $arr[$i - 1][$j] == 1)
$c++;
if ($j > 0 && $arr[$i][$j - 1] == 1)
$c++;
if ($i > 0 && $j > 0 && $arr[$i - 1][$j - 1] == 1)
$c++;
if ($i < $N - 1 && $arr[$i + 1][$j] == 1)
$c++;
if ($j < $N - 1 && $arr[$i][$j + 1] == 1)
$c++;
if ($i < $N - 1 && $j < $N - 1 &&
$arr[$i + 1][$j + 1] == 1)
$c++;
if ($i < $N - 1 && $j > 0 && $arr[$i + 1][$j - 1] == 1)
$c++;
if ($i > 0 && $j < $N - 1 && $arr[$i - 1][$j + 1] == 1)
$c++;
// Comparing the number of
// neighbouring 1s with
// given ranges
if ($arr[$i][$j] == 1)
{
if ($c >= $range1a && $c <= $range1b)
$b[$i][$j] = 1;
else
$b[$i][$j] = 0;
}
if ($arr[$i][$j] == 0) {
if ($c >= $range0a && $c <= $range0b)
$b[$i][$j] = 1;
else
$b[$i][$j] = 0;
}
}
}
// Copying changes to
// the main matrix
for ($k = 0; $k < $N; $k++)
for ($m = 0; $m < $N; $m++)
$arr[$k][$m] = $b[$k][$m];
}
return $b;
}
// Driver code
$N = 4;
$arr= array(array(0, 0, 0, 0),
array(0, 1, 1, 0),
array(0, 0, 1, 0),
array(0, 1, 0, 1));
$range1a = 2; $range1b = 2;
$range0a = 2; $range0b = 3;
$K = 3; $b = array(array(0));
// Function call to calculate
// the resultant matrix
// after 'K' iterations.
$b1 = predictMatrix($arr, $range1a, $range1b,
$range0a, $range0b, $K, $b);
// Printing Result
for ($i = 0; $i < $N; $i++)
{
echo "\n";
for ($j = 0; $j < $N; $j++)
echo $b1[$i][$j] . " ";
}
// This code is contributed by Akanksha Rai
Javascript
<script>
// Javascript implementation of the approach
// Dimension of Array
let N = 4 ;
function predictMatrix(arr,range1a,range1b,range0a,range0b,K,b)
{
// Count of 1s
let c = 0;
while (K != 0) {
K--;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
c = 0;
// Counting all neighbouring 1s
if (i > 0 && arr[i - 1][j] == 1)
c++;
if (j > 0 && arr[i][j - 1] == 1)
c++;
if (i > 0 && j > 0
&& arr[i - 1][j - 1] == 1)
c++;
if (i < N - 1 && arr[i + 1][j] == 1)
c++;
if (j < N - 1 && arr[i][j + 1] == 1)
c++;
if (i < N - 1 && j < N - 1
&& arr[i + 1][j + 1] == 1)
c++;
if (i < N - 1 && j > 0
&& arr[i + 1][j - 1] == 1)
c++;
if (i > 0 && j < N - 1
&& arr[i - 1][j + 1] == 1)
c++;
// Comparing the number of
// neighbouring 1s with
// given ranges
if (arr[i][j] == 1) {
if (c >= range1a && c <= range1b)
b[i][j] = 1;
else
b[i][j] = 0;
}
if (arr[i][j] == 0) {
if (c >= range0a && c <= range0b)
b[i][j] = 1;
else
b[i][j] = 0;
}
}
}
// Copying changes to
// the main matrix
for (let k = 0; k < N; k++)
for (let m = 0; m < N; m++)
arr[k][m] = b[k][m];
}
}
// Driver code
let arr = [[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 1, 0],
[0, 1, 0, 1]];
let range1a = 2, range1b = 2;
let range0a = 2, range0b = 3;
let K = 3;
let b = new Array(N) ;
for(let i=0;i<N;i++)
{
b[i]=new Array(N);
for(let j=0;j<N;j++)
{
b[i][j]=0;
}
}
// Function call to calculate
// the resultant matrix
// after 'K' iterations.
predictMatrix(arr, range1a, range1b,
range0a, range0b, K, b);
// Printing Result
for (let i = 0; i < N; i++) {
document.write("<br>");
for (let j = 0; j < N; j++)
document.write(b[i][j]+ " ");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0
Complejidad de tiempo: O(K*N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por Krishna_Yadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA