Beschrijving

Oefening op 5 punten

De kikker die we kennen uit de les is bijgelovig geworden. Hij wil weer naar zijn meertje geraken, maar hij wil geen vakjes met waarde 13 passeren. Onderweg mag hij alleen:

• een vakje naar rechts gaan;
• een vakje naar beneden gaan.

De waarde in het startvak is de beginwaarde van zijn pad.

Telkens hij naar een nieuw vakje gaat, telt hij de waarde van dat vakje op bij het totaal.

Bepaal welk pad van linksboven naar rechtsonder de kleinste eindwaarde oplevert, zonder ooit een vakje met waarde 13 te betreden.

Geef het getekende pad terug. Je mag ervan uitgaan dat elke test een oplossing heeft.

Maak gebruik van dynamisch programmeren.

Input

De functie krijgt één argument:

• matrix: een rechthoekige matrix met getallen tussen 13 en 25

Output

Geef een nieuwe matrix terug waarin elk vakje op het gekozen pad vervangen is door "X".

Voorbeeld

Beschouw de matrix:

[
    [18, 15, 15],
    [14, 13, 14]
]

De kleinste geldige route is:

[
    ["X", "X", "X"],
    [14, 13, "X"]
]

In dit voorbeeld kiest de kikker dus een pad met totaal 18 + 15 + 15 + 14 = 62 en vermijdt hij het vakje met waarde 13.