Anzahl der Pfade in einem Gitter
Angenommen, wir haben ein Gitter (Grid) mit der Höhe
h und der Breite w. Ziel ist es, die Anzahl der einzigartigen Wege zu berechnen, um von der oberen linken Ecke zur unteren rechten Ecke zu gelangen. Erlaubt sind dabei nur Bewegungen nach rechts oder nach unten.o | ➡️ | ㅤ | ㅤ |
⬇️ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Eingabe
Die Eingabe enthält zwei Ganzzahlen
h und w (1 ≤ h, w ≤ 100).Ausgabe
Das Programm soll die Anzahl aller möglichen eindeutigen Pfade von der oberen linken zur unteren rechten Ecke des Gitters ausgeben. Da das Ergebnis sehr groß werden kann, soll die Ausgabe modulo erfolgen.
Beispiele
Eingabe | Ausgabe |
2 3 | 3 |
3 4 | 10 |
7 3 | 28 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB