Идентичное разбиение в прямоугольной сетке

Опубликовано: 21 Июня, 2021

Учитывая размеры прямоугольной сетки NxM , задача состоит в том, чтобы найти минимальное количество разрезов, необходимых для разбиения данной прямоугольной сетки на квадрат размером 1 × 1 .

Примеры:

Input: N = 4, M = 4
Output: 15

Input: N = 2, M = 1
Output: 1

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

На изображениях выше показано разделение прямоугольной сетки. Мы можем заметить, что каждый разрез увеличивает количество прямоугольников разных размеров на 1 . Мы будем делать разбиение, пока не дойдем до квадрата размерности 1 × 1 .

Таким образом, для данных прямоугольных размеров NxM общее количество квадратов размером 1 × 1 равно N * M. Поэтому нам потребовалось N * M - 1 разрезов, чтобы разбить заданные прямоугольные размеры NxM на квадраты размером 1 × 1.

Ниже представлена реализация описанного выше подхода:

C ++




// 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




# 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 #




// 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
Выход:
15

Сложность времени: O (1)

Хотите учиться на лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для языка и STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .