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 keverslakken1, 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:

1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581

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:

1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581

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:

Voorbeeld

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

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

Epiloog

Nazarii Bardiuk (@nbardiuk4) animeerde zijn oplossing.