Anzahl der Pfade in einem Raster 2
Angenommen, wir haben ein Raster mit Höhe
h und Breite w. Gesucht ist die Anzahl eindeutiger Wege, um vom Feld oben links zum Feld unten rechts zu gelangen. Erlaubt sind dabei nur Bewegungen nach rechts, nach unten oder diagonal in Richtung rechts unten.o | ➡️ | ㅤ | ㅤ |
⬇️ | ↘ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Eingabe
Die Eingabe besteht aus zwei ganzen Zahlen
h und w (1 ≤ h, w ≤ 100).Ausgabe
Das Programm soll die Anzahl an möglichen eindeutigen Wegen von der oberen linken Ecke zur unteren rechten Ecke des Rasters ausgeben. Da das Ergebnis sehr groß sein kann, soll es modulo ausgegeben werden.
Beispiele
Eingabe | Ausgabe |
2 3 | 5 |
3 4 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB