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.

Gevraagd: Ontwerp en implementeer een algoritme dat via dynamisch programmeren de beste route bepaalt. Implementeer hiervoor de interface Manhattan¹ in een klasse genaamd DynamischManhattan. Hiervoor schrijf je een methode public List<Kruispunt> bepaalRoute(Kruispunt[][] rooster), die een 2-dimensionale array van kruispunten als argument heeft. De output is een beste route, voorgesteld als een lijst van kruispunten in de volgorde waarin ze bezocht zijn, inclusief het start- en eindpunt. Maak bij dit alles gebruik van de gegeven klasse Kruispunt². Een object van de klasse Kruispunt stelt een kruispunt van twee straten in Manhattan voor. Bij elk kruispunt 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.

De gegeven 2-dimensionale array rooster[n][m] bestaat uit n rijen in de noord-zuid richting en m rijen in de oost-west richting.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Opmerking

Het is niet toegestaan om de input rooster van de methode bepaalRouteaan te passen. Indien je dit wel doet, zal de test falen.