Je hebt bijna de uitgang van de grot bereikt, maar de wanden komen steeds dichter bij elkaar. Je onderzeeër kan er nauwelijks nog tussen. Het grootste probleem is echter dat de wanden van de grot vol zitten met keverslakken¹, en het is best om daar dus niet tegen te botsen.

De grot is groot, maar heeft een zeer laag plafond, waardoor je bewegingen beperkt blijven tot twee dimensies. De vorm van de grot lijkt op een vierkant, en een snelle scan van de densiteit van de keverslakken levert je een kaart op van het risiconiveau van de volledige grot (de invoer van deze opgave). Bijvoorbeeld:

Je begint op de positie linksboven en je bestemming is de positie rechtsonder. Daarbij kan je je niet diagonaal verplaatsen. Het cijfer op elke positie geeft het risiconiveau aan. Om het volledige risiconiveau van een route te bepalen, tel je de risiconiveaus op van alle posities die je betreedt (dat wil zeggen dat je het risiconiveau van je startpositie niet meetelt, tenzij je die opnieuw zou betreden; en positie verlaten verhoogt het totale risiconiveau niet).

Je opdracht bestaat erin om de route te vinden met het laagste totale risico. Voor het voorgaande voorbeeld hebben we hier de route met het laagste totale risico in het vet aangeduid:

Het totale risico van deze route is 40 (de startpositie wordt nooit betreden, dus het risico van deze positie wordt niet meegeteld).

Opgave

Wat is het laagste totale risico voor een route die linksboven begint en rechtsonder eindigt? Bepaal dit op de volgende manier:

Schrijf een functie riskLevel waaraan de padnaam (String) moet doorgegeven worden van een tekstbestand met de kaart van het risiconiveau van een grot. De functie moet het laagste risico (int) teruggeven voor een route die linksboven begint en rechtsonder eindigt.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden cave01.txt² en cave02.txt³ zich in de huidige directory bevinden.

> Submission.riskLevel("cave01.txt")
40
> Submission.riskLevel("cave02.txt")
415

Epiloog

Nazarii Bardiuk (@nbardiuk⁴) animeerde zijn oplossing.