División idéntica en una cuadrícula rectangular

Dada una cuadrícula rectangular de dimensiones NxM , la tarea es encontrar el número mínimo de cortes necesarios para romper la cuadrícula rectangular dada en un cuadrado de tamaño 1×1 .

Ejemplos: 

Entrada: N = 4, M = 4 
Salida: 15

Entrada: N = 2, M = 1 
Salida: 1 

Acercarse:  

Las imágenes de arriba muestran la división de la cuadrícula rectangular. Podemos observar que cada corte individual aumenta en 1 el número de rectángulos de diferentes dimensiones . Haremos el desdoblamiento hasta llegar al cuadrado de dimensión 1×1 .
Entonces, para las dimensiones rectangulares dadas de NxM, el número total de cuadrados de dimensiones 1×1 es N*M. Por lo tanto, requerimos N*M – 1 cortes para dividir las dimensiones rectangulares dadas de NxM en cuadrados de dimensión 1×1.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program of the above approach
#include <iostream>
using namespace std;
 
// Function to find the minimum cuts
void minimumCuts(int N, int M)
{
 
    // Print the minimum cuts using
    // the formula
    cout << (N * M - 1);
}
 
// Driver Code
int main()
{
 
    // Given dimensions
    int N = 4, M = 4;
 
    // Function call
    minimumCuts(N, M);
 
    return 0;
}

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum cuts
static void minimumCuts(int N, int M)
{
     
    // Print the minimum cuts using
    // the formula
    System.out.print(N * M - 1);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given dimensions
    int N = 4, M = 4;
 
    // Function call
    minimumCuts(N, M);
}
}
 
// This code is contributed by Rohit_ranjan

# Python3 program of the above approach
 
# Function to find the minimum cuts
def minimumCuts(N, M):
     
    # Print the minimum cuts using
    # the formula
    print(N * M - 1)
 
# Driver Code
if __name__ == "__main__":
     
    # Given dimensions
    N = 4
    M = 4
     
    # Function call
    minimumCuts(N, M)
     
# This code is contributed by coder001

// C# program of the above approach
using System;
 
class GFG{
 
// Function to find the minimum cuts
static void minimumCuts(int N, int M)
{
     
    // Print the minimum cuts using
    // the formula
    Console.Write(N * M - 1);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given dimensions
    int N = 4, M = 4;
 
    // Function call
    minimumCuts(N, M);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program of the above approach
 
// Function to find the minimum cuts
function minimumCuts(N, M)
{
 
    // Print the minimum cuts using
    // the formula
    document.write(N * M - 1);
}
 
// Driver Code
// Given dimensions
var N = 4, M = 4;
 
// Function call
minimumCuts(N, M);
 
// This code is contributed by noob2000.
</script>

15

Complejidad de tiempo: O(1)