Идентичное разбиение в прямоугольной сетке
Учитывая размеры прямоугольной сетки NxM , задача состоит в том, чтобы найти минимальное количество разрезов, необходимых для разбиения данной прямоугольной сетки на квадрат размером 1 × 1 .
Примеры:
Input: N = 4, M = 4
Output: 15Input: 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 cutsvoid minimumCuts( int N, int M){ // Print the minimum cuts using // the formula cout << (N * M - 1);} // Driver Codeint main(){ // Given dimensions int N = 4, M = 4; // Function call minimumCuts(N, M); return 0;} |
Ява
// Java program of the above approachimport java.util.*; class GFG{ // Function to find the minimum cutsstatic void minimumCuts( int N, int M){ // Print the minimum cuts using // the formula System.out.print(N * M - 1 );} // Driver Codepublic 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 cutsdef minimumCuts(N, M): # Print the minimum cuts using # the formula print (N * M - 1 ) # Driver Codeif __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 approachusing System; class GFG{ // Function to find the minimum cutsstatic void minimumCuts( int N, int M){ // Print the minimum cuts using // the formula Console.Write(N * M - 1);} // Driver Codepublic 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)