Dada una array mat[][] de dimensiones N*M y un número entero positivo K , la tarea es encontrar el número de celdas en una cuadrícula a partir de la cual se puede alcanzar el máximo de celdas mediante K saltos en dirección vertical u horizontal.
Ejemplos:
Entrada: N = 3, M = 3, K = 2
Salida: 4
Explicación:
Las celdas representadas como X son las celdas a partir de las cuales se puede alcanzar el máximo de celdas (= 2) mediante K (= 2) saltos:
XOX
OOO
XOXEntrada: N = 5, M = 5, K = 2
Salida: 9
Enfoque: el problema dado se puede resolver contando el número de celdas posibles para las filas y columnas por separado en función de las siguientes observaciones:
- Considere cualquier fila, digamos i tal que i <= K , entonces el número de filas desde i que se pueden alcanzar usando saltos de K es (N – i) / K + 1 .
- Si las filas dicen que i es i > K , entonces estas celdas están conectadas a alguna fila X donde X <= K , por lo que ya están consideradas.
Por lo tanto, a partir de las observaciones anteriores, la idea es encontrar el recuento de filas que están conectadas al número máximo de filas en una variable, digamos count_R . De manera similar, para las columnas, busque el recuento de columnas que están conectadas al máximo de columnas en una variable, digamos count_C .
Ahora, el número de celdas en la cuadrícula tal que se puede alcanzar la celda máxima desde esa celda con un salto de K en la dirección vertical u horizontal está dado por (count_R)*(count_C) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of cells
// in the grid such that maximum cell is
// reachable with a jump of K
long long countCells(int n, int m, int s)
{
// Maximum reachable rows
// from the current row
int mx1 = -1;
// Stores the count of cell that are
// reachable from the current row
int cont1 = 0;
for (int i = 0; i < s && i < n; ++i) {
// Count of reachable rows
int aux = (n - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx1) {
mx1 = cont1 = aux;
}
// Add it to the count
else if (aux == mx1)
cont1 += aux;
}
// Maximum reachable columns from
// the current column
int mx2 = -1;
// Stores the count of cell that are
// reachable from the current column
int cont2 = 0;
for (int i = 0; i < s && i < m; ++i) {
// Count of rechable columns
int aux = (m - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx2)
mx2 = cont2 = aux;
// Add it to the count
else if (aux == mx2)
cont2 += aux;
}
// Return the total count of cells
return (long long)(cont1 * cont2);
}
// Driver Code
int main()
{
int N = 5, M = 5, K = 2;
cout << countCells(N, M, K);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to count the number of cells
// in the grid such that maximum cell is
// reachable with a jump of K
public static long countCells(int n, int m, int s)
{
// Maximum reachable rows
// from the current row
int mx1 = -1;
// Stores the count of cell that are
// reachable from the current row
int cont1 = 0;
for (int i = 0; i < s && i < n; ++i) {
// Count of reachable rows
int aux = (n - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx1) {
mx1 = cont1 = aux;
}
// Add it to the count
else if (aux == mx1)
cont1 += aux;
}
// Maximum reachable columns from
// the current column
int mx2 = -1;
// Stores the count of cell that are
// reachable from the current column
int cont2 = 0;
for (int i = 0; i < s && i < m; ++i) {
// Count of rechable columns
int aux = (m - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx2)
mx2 = cont2 = aux;
// Add it to the count
else if (aux == mx2)
cont2 += aux;
}
// Return the total count of cells
return (long) (cont1 * cont2);
}
// Driver Code
public static void main(String args[]) {
int N = 5, M = 5, K = 2;
System.out.println(countCells(N, M, K));
}
}
// This code is contributed by gfgking.
Python3
# Python 3 program for the above approach # Function to count the number of cells # in the grid such that maximum cell is # reachable with a jump of K def countCells(n, m, s): # Maximum reachable rows # from the current row mx1 = -1 # Stores the count of cell that are # reachable from the current row cont1 = 0 i = 0 while(i < s and i < n): # Count of reachable rows aux = (n - (i + 1)) // s + 1 # Update the maximum value if (aux > mx1): mx1 = cont1 = aux # Add it to the count elif(aux == mx1): cont1 += aux i += 1 # Maximum reachable columns from # the current column mx2 = -1 # Stores the count of cell that are # reachable from the current column cont2 = 0 i = 0 while(i < s and i < m): # Count of rechable columns aux = (m - (i + 1)) // s + 1 # Update the maximum value if (aux > mx2): mx2 = cont2 = aux # Add it to the count elif(aux == mx2): cont2 += aux i += 1 # Return the total count of cells return cont1 * cont2 # Driver Code if __name__ == '__main__': N = 5 M = 5 K = 2 print(countCells(N, M, K)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of cells
// in the grid such that maximum cell is
// reachable with a jump of K
static int countCells(int n, int m, int s)
{
// Maximum reachable rows
// from the current row
int mx1 = -1;
// Stores the count of cell that are
// reachable from the current row
int cont1 = 0;
for (int i = 0; i < s && i < n; ++i) {
// Count of reachable rows
int aux = (n - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx1) {
mx1 = cont1 = aux;
}
// Add it to the count
else if (aux == mx1)
cont1 += aux;
}
// Maximum reachable columns from
// the current column
int mx2 = -1;
// Stores the count of cell that are
// reachable from the current column
int cont2 = 0;
for (int i = 0; i < s && i < m; ++i) {
// Count of rechable columns
int aux = (m - (i + 1)) / s + 1;
// Update the maximum value
if (aux > mx2)
mx2 = cont2 = aux;
// Add it to the count
else if (aux == mx2)
cont2 += aux;
}
// Return the total count of cells
return (cont1 * cont2);
}
// Driver Code
public static void Main()
{
int N = 5, M = 5, K = 2;
Console.Write(countCells(N, M, K));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of cells
// in the grid such that maximum cell is
// reachable with a jump of K
function countCells(n, m, s)
{
// Maximum reachable rows
// from the current row
let mx1 = -1;
// Stores the count of cell that are
// reachable from the current row
let cont1 = 0;
for (let i = 0; i < s && i < n; ++i) {
// Count of reachable rows
let aux = Math.floor((n - (i + 1)) / s + 1);
// Update the maximum value
if (aux > mx1) {
mx1 = cont1 = aux;
}
// Add it to the count
else if (aux == mx1) cont1 += aux;
}
// Maximum reachable columns from
// the current column
let mx2 = -1;
// Stores the count of cell that are
// reachable from the current column
let cont2 = 0;
for (let i = 0; i < s && i < m; ++i) {
// Count of rechable columns
let aux = Math.floor((m - (i + 1)) / s + 1);
// Update the maximum value
if (aux > mx2) mx2 = cont2 = aux;
// Add it to the count
else if (aux == mx2) cont2 += aux;
}
// Return the total count of cells
return cont1 * cont2;
}
// Driver Code
let N = 5,
M = 5,
K = 2;
document.write(countCells(N, M, K));
// This code is contributed by gfgking.
</script>
Producción:
9
Complejidad temporal: O(N + M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA