Gegeven is een rechthoekig rooster met \(n\) rijen en \(m\) kolommen van verbindingen van dezelfde lengte. Bepaalde kruispunten zijn echter niet toegankelijk. Gevraagd is het aantal verschillende kortste routes te bepalen van het hoekpunt \((0,0)\) naar het hoekpunt \((n-1,m-1)\).

Bijvoorbeeld, onderstaand rooster met 4 rijen en 7 kolommen heeft 18 verschillende routes van \(H=(0,0)\) naar \(P=(3,6)\).

Opgave

Schrijf een Python-functie bepaalAantalKortsteRoutes die als parameters het aantal rijen \(n\) en het aantal kolommen \(m\) van het rooster krijgt, evenals een lijst van coordinaten van geblokkeerde kruispunten. De functie moet het aantal verschillende kortste routes van \((0,0)\) naar \((n-1,m-1)\) teruggeven.

Voorbeelden

>>> bepaalAantalKortsteRoutes(4,7,[(0,4),(1,2),(3,3)])
18
>>> bepaalAantalKortsteRoutes(5,8,[(1,1),(3,4),(4,6),(2,7)])
27
>>> bepaalAantalKortsteRoutes(10,15,[(2,3),(4,5),(6,9),(9,10),(7,8),(2,6),(7,3),(9,13),(1,2)])
32464
>>> bepaalAantalKortsteRoutes(5,5,[(4,0),(3,1),(2,2),(1,3),(0,4)])
0
>>> bepaalAantalKortsteRoutes(10,15,[(2,2),(6,4),(4,7),(8,10)])
242774
>>> bepaalAantalKortsteRoutes(15,20,[(3,4),(6,5),(1,5),(8,2),(12,19),(14,7),(13,4)])
266273165
>>> bepaalAantalKortsteRoutes(10,15,[])
817190