Gegeven is een rooster waarbij je van het aantal wegen in een rooster moet tellen van linksboven naar rechtsonder. Je mag hierbij enkel naar rechts en naar onder bewegen. De grijze blokjes stellen obstakels voor.

Dergelijk rooster wordt voorgesteld met behulp van een twee-dimensionale lijst bestaande uit de getallen 0 of 1. Een 1 stelt een obstakel voor.

Stel dat je via een bepaald vakje moet bewegen, hoeveel mogelijke wegen zijn er dan van A naar B, via X?

Gevraagd

Schrijf een functie aantal_via(rooster, coordinaat) die gegeven een rooster en een coordinaat als een tupel het aantal wegen van A naar B via, die coördinaat telt en retourneert.

Voorbeelden

>>> aantal_via([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1], 
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1],
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], (2,5))
4

>>> aantal_via([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1], 
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], (2,3))
3

Tips

• Kopieer de functie aantal_wegen() uit de vorige oefening.

• Bereken het aantal wegen van A naar X en van X naar B… Maak dus twee aparte roosters, linksboven (van linksboven tot en met X), rechtsboven (van X tot en met rechtsonder) en gebruik dan aantal_wegen(linksboven) en aantal_wegen(rechtsonder).

• Nadien is het antwoord gemakkelijk te bepalen.

Bron

Gebaseerd op vraag 2 uit beOI 2024.