Problem
Beginne in der linken oberen Ecke eines Gitters mit rows Zeilen und columns Spalten von Zellen. Bewege dich nur entlang der Zellkanten, jeweils einen Schritt nach rechts oder einen Schritt nach unten, bis du die rechte untere Ecke erreichst. Zähle alle unterschiedlichen Zugfolgen. Das Gitter enthält keine Hindernisse.
Ein Gitter mit 2 Zeilen und 3 Spalten benötigt genau 2 Züge nach unten und 3 Züge nach rechts.
Implementiere lattice_paths(rows, columns).
Eingabe
rows: Die Anzahl der Zellzeilen, nicht der Ecken.
columns: Die Anzahl der Zellspalten, nicht der Ecken.
Ausgabe
Gib die Anzahl der möglichen Routen von Ecke zu Ecke zurück.
Einschränkungen
0 ≤ rows, columns ≤ 30 und rows + columns ≤ 60. Null in einer Dimension ergibt eine gerade Route. Ein 0 × 0 Gitter hat genau eine leere Route. Die Anzahl passt in ein vorzeichenbehaftetes 64-Bit-Integer.
Beispiele
Eingabe:
rows = 2
columns = 3
Erwartete Ausgabe:
expected = 10Eingabe:
long long rows = 2;
long long columns = 3;
Erwartete Ausgabe:
long long expected = 10;Eingabe:
long rows = 2;
long columns = 3;
Erwartete Ausgabe:
long expected = 10;Erläuterung
Jede Route besteht aus fünf Zügen. Es gibt zehn verschiedene Möglichkeiten, zwei davon nach unten zu wählen.
Eingabe:
rows = 0
columns = 4
Erwartete Ausgabe:
expected = 1Eingabe:
long long rows = 0;
long long columns = 4;
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long rows = 0;
long columns = 4;
Erwartete Ausgabe:
long expected = 1;Erläuterung
Es gibt nur die gerade Route mit vier Zügen nach rechts.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jeder Weg ist nur eine Anordnung der nötigen Ab- und Rechts-Schritte.
Hinweis 2
Zähle, auf wie viele Arten du die Positionen einer Schrittart unter allen Schritten wählen kannst, statt die Wege einzeln zu durchsuchen.
Hinweis 3
Achte auf die entarteten Gitter: Wenn eine Dimension 0 ist, gibt es genau einen geraden Weg, und ein 0×0-Gitter hat ebenfalls einen leeren Weg.
Erwartete Komplexität
Zeit O(min(rows, columns)), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.