Dada una array N * M y una posición inicial (X, Y) de un virus, la tarea es averiguar el número de células cubiertas después de D días, si el virus se propaga desde su celda actual a sus células adyacentes todos los días.
Ejemplos:
Entrada: N = 5, M = 5, X = 1, Y = 3, D = 3
Salida: 15
Explicación:
Podemos ver claramente en la imagen que 15 celdas están cubiertas después de 3 días.
Entrada: N = 10, M = 10, X = 7, Y = 8, D = 4
Salida: 42
Explicación:
Al hacer una array N * M y llenar las celdas adyacentes durante 4 días obtendremos 42 celdas cubiertas.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos observar claramente que desde una celda inicial, solo necesitamos encontrar la extensión de las celdas hacia arriba, derecha, abajo e izquierda después de D días. Luego calcule el total de celdas dentro de cada cuadrilátero de celdas formadas y súmelas todas.
Por lo tanto, la respuesta total será la suma de todas las celdas de los cuadriláteros después de D días + el total de celdas que se encuentran en la parte superior, derecha, abajo, izquierda y 1 (para la celda de inicio), teniendo en cuenta los límites del cuadrilátero.
A continuación se muestra la condición para la extensión en las cuatro direcciones:
Extensión hasta Arriba -> min(D, X-1)
Extensión hasta Abajo -> min(D, NX)
Extensión hasta Izquierda -> min(D, Y-1)
Extensión hasta Derecha -> min(D, MY)
Mire la imagen a continuación para una comprensión clara:
Ahora multiplique Arriba * Izquierda , Arriba * Derecha , Abajo * Izquierda , Abajo * Derecha y súmelos todos y también sume el total de celdas a lo largo de la línea de 4 direcciones. También sumamos 1 (para la celda inicial) para obtener las celdas resultantes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Total number of cells covered
// in a matrix after D days
#include <bits/stdc++.h>
using namespace std;
// Function to return the total
// infected cells after d days
int solve(int n, int m, int x,
int y, int d)
{
// Top extension
int top = min(d, x - 1);
// Bottom extension
int down = min(d, n - x);
// Left extension
int left = min(d, y - 1);
// Right extension
int right = min(d, m - y);
// Calculating the cells
// in each quadrilateral
int quad1 = top * left;
int quad2 = left * down;
int quad3 = down * right;
int quad4 = right * top;
// Sum all of them to get
// total cells in each
// quadrilateral
int totalsq = quad1 + quad2
+ quad3 + quad4;
// Add the singleblocks
// along the lines of top,
// down, left, right
int singleBlocks = top + down
+ left + right + 1;
// Return the ans
return totalsq + singleBlocks;
}
// Driver code
int main()
{
int n, m, x, y, d;
// Dimensions of cell
n = 10, m = 10;
// Starting Coordinates
x = 7, y = 8;
// Number of Days
d = 4;
d--;
// Function Call
cout << solve(n, m, x, y, d);
}
Java
// Java implementation to find the
// total number of cells covered
// in a matrix after D days
import java.util.*;
class GFG{
// Function to return the total
// infected cells after d days
static int solve(int n, int m, int x,
int y, int d)
{
// Top extension
int top = Math.min(d, x - 1);
// Bottom extension
int down = Math.min(d, n - x);
// Left extension
int left = Math.min(d, y - 1);
// Right extension
int right = Math.min(d, m - y);
// Calculating the cells
// in each quadrilateral
int quad1 = top * left;
int quad2 = left * down;
int quad3 = down * right;
int quad4 = right * top;
// Sum all of them to get
// total cells in each
// quadrilateral
int totalsq = quad1 + quad2 +
quad3 + quad4;
// Add the singleblocks
// along the lines of top,
// down, left, right
int singleBlocks = top + down +
left + right + 1;
// Return the ans
return totalsq + singleBlocks;
}
// Driver code
public static void main(String[] args)
{
// Dimensions of cell
int n = 10, m = 10;
// Starting coordinates
int x = 7, y = 8;
// Number of days
int d = 4;
d--;
// Function call
System.out.println(solve(n, m, x, y, d));
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 implementation to find the # total number of cells covered in # a matrix after D days # Function to return the total # infected cells after d days def solve(n, m, x, y, d): # Top extension top = min(d, x - 1) # Bottom extension down = min(d, n - x) # Left extension left = min(d, y - 1) # Right extension right = min(d, m - y) # Calculating the cells # in each quadrilateral quad1 = top * left quad2 = left * down quad3 = down * right quad4 = right * top # Sum all of them to get # total cells in each # quadrilateral totalsq = (quad1 + quad2 + quad3 + quad4) # Add the singleblocks # along the lines of top, # down, left, right singleBlocks = (top + down + left + right + 1) # Return the ans return totalsq + singleBlocks # Driver Code if __name__ == '__main__': # Dimensions of cell n = 10 m = 10 # Starting Coordinates x = 7 y = 8 # Number of Days d = 4 d -= 1 # Function Call print(solve(n, m, x, y, d)) # This code is contributed by Shivam Singh
C#
// C# implementation to find the
// total number of cells covered
// in a matrix after D days
using System;
class GFG{
// Function to return the total
// infected cells after d days
static int solve(int n, int m, int x,
int y, int d)
{
// Top extension
int top = Math.Min(d, x - 1);
// Bottom extension
int down = Math.Min(d, n - x);
// Left extension
int left = Math.Min(d, y - 1);
// Right extension
int right = Math.Min(d, m - y);
// Calculating the cells
// in each quadrilateral
int quad1 = top * left;
int quad2 = left * down;
int quad3 = down * right;
int quad4 = right * top;
// Sum all of them to get
// total cells in each
// quadrilateral
int totalsq = quad1 + quad2 +
quad3 + quad4;
// Add the singleblocks
// along the lines of top,
// down, left, right
int singleBlocks = top + down +
left + right + 1;
// Return the ans
return totalsq + singleBlocks;
}
// Driver code
public static void Main(String[] args)
{
// Dimensions of cell
int n = 10, m = 10;
// Starting coordinates
int x = 7, y = 8;
// Number of days
int d = 4;
d--;
// Function call
Console.WriteLine(solve(n, m, x, y, d));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript implementation to find the
// total number of cells covered
// in a matrix after D days
// Function to return the total
// infected cells after d days
function solve(n, m, x, y, d)
{
// Top extension
let top = Math.min(d, x - 1);
// Bottom extension
let down = Math.min(d, n - x);
// Left extension
let left = Math.min(d, y - 1);
// Right extension
let right = Math.min(d, m - y);
// Calculating the cells
// in each quadrilateral
let quad1 = top * left;
let quad2 = left * down;
let quad3 = down * right;
let quad4 = right * top;
// Sum all of them to get
// total cells in each
// quadrilateral
let totalsq = quad1 + quad2 +
quad3 + quad4;
// Add the singleblocks
// along the lines of top,
// down, left, right
let singleBlocks = top + down +
left + right + 1;
// Return the ans
return totalsq + singleBlocks;
}
// Driver Code
// Dimensions of cell
let n = 10, m = 10;
// Starting coordinates
let x = 7, y = 8;
// Number of days
let d = 4;
d--;
// Function call
document.write(solve(n, m, x, y, d));
// This code is contributed by sanjoy_62.
</script>
42
Complejidad de tiempo: O(1)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA