Een toerist bezoekt Manhattan en wil een wandeling maken die langs zoveel mogelijk toeristische attracties passeert. De straten in Manhattan vormen een perfect rooster. De toerist start in de noord-west hoek en eindigt in de zuid-oost hoek van dit rooster, waarbij hij zich enkel naar het oosten en naar het zuiden verplaatst. Op elk kruispunt kiest hij in welk van deze twee richtingen hij zijn weg zal verderzetten.

In elke straat tussen twee kruispunten liggen een gekend aantal toeristische attracties. De bedoeling is om de som van deze aantallen over alle bewandelde straten te maximaliseren.

Opgave

Ontwerp en implementeer een algoritme dat via dynamisch programmeren de beste route bepaalt. Implementeer hiervoor een Python-functie bepaalRoute(kruispunten: list) die een 2-dimensionale array van kruispunten als argument heeft. De output is de beste route, voorgesteld als een lijst van kruispunten in de volgorde waarin ze bezocht zijn, inclusief start- en eindpunt. Bij elk kruispunt, voorgesteld als een tuple tuple(noordelijke attracties, westelijke attracties) kan zowel het aantal attracties opgevraagd worden dat zich tussen het gegeven kruispunt en het dichtstbijzijnde noordelijke kruispunt bevindt, als het aantal attracties dat zich tussen het gegeven kruispunt en het dichtstbijzijnde westelijke kruispunt bevindt.

Voorbeelden

>>> bepaalRoute([[(0, 0), (0, 4)], [(5, 0), (8, 6)]])
[(0, 0), (0, 1), (1, 1)]
>>> bepaalRoute([[(0, 0), (0, 1), (0, 2)], [(2, 0), (9, 4), (5, 3)]])
[(0, 0), (0, 1), (1, 1), (1, 2)]
>>> bepaalRoute([[(0, 0), (0, 1), (0, 7)], [(22, 0), (20, 20), (50, 1)], [(20, 0), (10, 3), (3, 5)]])
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]