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 DynamicManhattan. Hiervoor schrijf je een methode public List<Crossing> findRoute(Crossing[][] grid), 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 record Crossing. Een object van de klasse Crossing 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.

Gegeven is een 2-dimensionale array grid[n][m] met \(n\) rijen en \(m\) kolommen die het rooster voorstelt. Het element grid[0][0] is hierbij het meest noord-westelijke kruispunt van het rooster. De noord-zuid richting wordt bepaald door de eerste index en de oost-west richting door de tweede index. Zo ligt grid[i][j] ten noorden van grid[i + 1][j] en ten westen van grid[i][j + 1].

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 grid van de methode findRouteaan te passen. Indien je dit wel doet, zal de test falen.