A tourist visits Manhatten and wants to walk past as many touristic attractions as possible. The streets of Manhatten form a perfect grid. The tourist starts in the north-west corner and ends in the south-east corner of the grid. The tourist can only move east and south. On every intersection he can choose between two directions. In every street between two intersections are a few attractions. In this problem you want to maximize the sum of seen attractions from start to finish.

Exercise

Design and implement an algorithm using dynamic programming that finds the optimal path. Implement a Python-functionfindPath(kruispunten: list) that receives a 2-dimensional array of intersections as it’s argument. The output is the best path, represented as a list of intersections in order of visitation, including the start and end point. Every intersection is represented as a tuple tuple(northern attractions, southern attractions).

Examples

>>> findPath([[(0, 0), (0, 4)], [(5, 0), (8, 6)]])
[(0, 0), (0, 1), (1, 1)]
>>> findPath([[(0, 0), (0, 1), (0, 2)], [(2, 0), (9, 4), (5, 3)]])
[(0, 0), (0, 1), (1, 1), (1, 2)]
>>> findPath([[(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)]