Número mínimo de puntos necesarios para cubrir todos los bloques de una cuadrícula 2D

Dados dos enteros N y M . La tarea es encontrar el número mínimo de puntos necesarios para cubrir una cuadrícula  N * M.
 

Un punto puede cubrir dos bloques en una cuadrícula 2D cuando se coloca en cualquier línea común o lateral.

Ejemplos: 
 

Entrada: N = 5, M = 7 
Salida: 18
Entrada: N = 3, M = 8 
Salida: 12 
 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . La idea principal es observar que un solo punto colocado en la línea común o lateral cubre dos bloques. Entonces, el número total de puntos necesarios para cubrir todos los bloques (por ejemplo , B bloques ) es B/2 cuando B es par o B/2 + 1 cuando B es impar.
Para una cuadrícula que tenga N*M bloques, el número total de bloques será (N*M)/2 cuando cualquiera de ellos sea par. De lo contrario, requerirá ((N*M)/2) + 1 puntos para cubrir todos los bloques y uno adicional para el último bloque intacto.
A continuación se muestra la imagen para mostrar cómo se pueden usar los puntos para cubrir bloques en una cuadrícula 2D: 
 

El punto ‘A’ cubre dos bloques y ‘B’ cubre un bloque.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of Points required to cover a grid
int minPoints(int n, int m)
{
    int ans = 0;
 
    // If number of block is even
    if ((n % 2 != 0)
        && (m % 2 != 0)) {
        ans = ((n * m) / 2) + 1;
    }
    else {
        ans = (n * m) / 2;
    }
 
    // Return the minimum points
    return ans;
}
 
// Driver Code
int main()
{
    // Given size of grid
    int N = 5, M = 7;
 
    // Function Call
    cout << minPoints(N, M);
    return 0;
}

// Java program for the above approach
class GFG{
     
// Function to find the minimum number
// of Points required to cover a grid
static int minPoints(int n, int m)
{
    int ans = 0;
 
    // If number of block is even
    if ((n % 2 != 0) && (m % 2 != 0))
    {
        ans = ((n * m) / 2) + 1;
    }
    else
    {
        ans = (n * m) / 2;
    }
 
    // Return the minimum points
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    // Given size of grid
    int N = 5, M = 7;
 
    // Function Call
    System.out.print(minPoints(N, M));
}
}
 
// This code is contributed by Ritik Bansal

# Python3 program for the above approach
 
# Function to find the minimum number
# of Points required to cover a grid
def minPoints(n, m):
 
    ans = 0
 
    # If number of block is even
    if ((n % 2 != 0) and (m % 2 != 0)):
        ans = ((n * m) // 2) + 1
 
    else:
        ans = (n * m) // 2
 
    # Return the minimum points
    return ans
 
# Driver code
if __name__ == '__main__':
 
    # Given size of grid
    N = 5
    M = 7
 
    # Function call
    print(minPoints(N, M))
 
# This code is contributed by himanshu77

// C# program for the above approach
using System;
class GFG{
     
// Function to find the minimum number
// of Points required to cover a grid
static int minPoints(int n, int m)
{
    int ans = 0;
 
    // If number of block is even
    if ((n % 2 != 0) && (m % 2 != 0))
    {
        ans = ((n * m) / 2) + 1;
    }
    else
    {
        ans = (n * m) / 2;
    }
 
    // Return the minimum points
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given size of grid
    int N = 5, M = 7;
 
    // Function Call
    Console.Write(minPoints(N, M));
}
}
 
// This code is contributed by sapnasingh4991

<script>
// Javascript implementation for the above approach
 
// Function to find the minimum number
// of Points required to cover a grid
function minPolets(n, m)
{
    let ans = 0;
 
    // If number of block is even
    if ((n % 2 != 0) && (m % 2 != 0))
    {
        ans = Math.floor((n * m) / 2) + 1;
    }
    else
    {
        ans = Math.floor((n * m) / 2);
    }
 
    // Return the minimum points
    return ans;
}
 
    // Driver Code
     
    // Given size of grid
    let N = 5, M = 7;
 
    // Function Call
    document.write(minPolets(N, M));
 
</script>

18

Tiempo Complejidad: O(1)  
Espacio Auxiliar: O(1)