समस्या
हर चाल में, एक आयत चुनें और उसे उसके किसी एक पक्ष के समानांतर पूरी तरह काटें, जिससे दो आयत बनें जिनकी भुजाएँ धनात्मक पूर्णांक हों। यह प्रक्रिया तब तक दोहराएँ जब तक हर टुकड़ा एक वर्ग न बन जाए। वर्गों के आकार अलग-अलग हो सकते हैं। टुकड़ों की नहीं, केवल कट की संख्या गिनें।
rectangle_cutting(height, width) को लागू करें।
इनपुट
height: प्रारंभिक आयत की ऊँचाई।
width: प्रारंभिक आयत की चौड़ाई।
आउटपुट
न्यूनतम कट की संख्या लौटाएँ।
सीमाएँ
1 ≤ height, width ≤ 500। घुमाने से उत्तर नहीं बदलता।
उदाहरण
इनपुट:
width = 3
height = 2
अपेक्षित आउटपुट:
expected = 2इनपुट:
long long width = 3;
long long height = 2;
अपेक्षित आउटपुट:
long long expected = 2;इनपुट:
long width = 3;
long height = 2;
अपेक्षित आउटपुट:
long expected = 2;व्याख्या
2 × 2 का एक वर्ग काट लें, शेष में 2 × 1 का आयत बचेगा। एक और कट से शेष को दो इकाई वर्गों में बाँट सकते हैं।
इनपुट:
width = 4
height = 4
अपेक्षित आउटपुट:
expected = 0इनपुट:
long long width = 4;
long long height = 4;
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long width = 4;
long height = 4;
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
प्रारंभिक आयत पहले से ही एक वर्ग है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Rectangle को दो छोटे rectangles में split करके और उनके best answers मिलाकर solve किया जा सकता है.
संकेत 2
Minimum पाने के लिए हर possible horizontal और vertical cut try करो.
संकेत 3
Memoization या table मददगार है, क्योंकि कई subrectangles बार-बार आते हैं.
अपेक्षित जटिलता
समय O(h*w*(h+w)), अतिरिक्त स्थान O(h*w)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।