Problem
Wähle bei jedem Zug ein Rechteck aus und schneide es vollständig, parallel zu einer Seite, sodass zwei Rechtecke mit positiven ganzzahligen Seitenlängen entstehen. Fahre fort, bis jedes Teilstück ein Quadrat ist. Die Quadrate dürfen unterschiedlich groß sein. Zähle die Schnitte, nicht die Stücke.
Implementiere rectangle_cutting(height, width).
Eingabe
height: Die Höhe des Startrechtecks.
width: Die Breite des Startrechtecks.
Ausgabe
Gib die minimale Anzahl der benötigten Schnitte zurück.
Einschränkungen
1 ≤ height, width ≤ 500. Eine Drehung verändert die Antwort nicht.
Beispiele
Eingabe:
width = 3
height = 2
Erwartete Ausgabe:
expected = 2Eingabe:
long long width = 3;
long long height = 2;
Erwartete Ausgabe:
long long expected = 2;Eingabe:
long width = 3;
long height = 2;
Erwartete Ausgabe:
long expected = 2;Erläuterung
Schneide ein 2 × 2 Quadrat ab, es bleibt ein 2 × 1 Rechteck übrig. Ein weiterer Schnitt teilt den Rest in zwei Einheitsquadrate.
Eingabe:
width = 4
height = 4
Erwartete Ausgabe:
expected = 0Eingabe:
long long width = 4;
long long height = 4;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long width = 4;
long height = 4;
Erwartete Ausgabe:
long expected = 0;Erläuterung
Das Startrechteck ist bereits ein Quadrat.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Ein Rechteck lässt sich lösen, indem du es in zwei kleinere Rechtecke teilst und deren beste Antworten kombinierst.
Hinweis 2
Probiere jeden möglichen horizontalen und vertikalen Schnitt aus, um das Minimum zu finden.
Hinweis 3
Memoization oder eine Tabelle hilft, weil viele Teilrechtecke mehrfach vorkommen.
Erwartete Komplexität
Zeit O(h*w*(h+w)), zusätzlicher Speicher O(h*w)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.