#!/usr/bin/perl

$filename = "15.txt";

open(FILE, $filename);
@data = <FILE>;
close(FILE);


$part1 = 1; #set this to 1 to solve for part1 of puzzle.

for ($i = 0; $i < $#data + 1; $i++) {
        $line = $data[$i];
        $line =~ s/[^0-9]*//sgi;
        @coords = split("", $line);
        if ($part1 == 1) {
                $maxx = $#coords + 1;
                $maxy = $#data + 1;
                for ($v = 0; $v < $#coords + 1; $v++) {
                        $map[$v][$i] = $coords[$v];
                        $distance[$v][$i] = 1000000;
                        $unvisited{$v.",".$i} = 1;
                }

        }
        else
        {
                $maxx = ($#coords + 1) * 5;
                $maxy = ($#data + 1) * 5;
                $ac = $#data + 1;
                $bc = $#coords + 1;
                for ($v = 0; $v < $#coords + 1; $v++) {

                        for ($m = 0; $m < 5; $m++) { #expand 5*5
                        for ($n = 0; $n < 5; $n++) {
                                $uval = $coords[$v] + $m + $n;
                                if ($uval > 9) {
                                        $uval = $uval - 9;
                                }

                                $map[$v + ($bc * $m)][$i + ($ac * $n)] = $uval;
                                $distance[$v + ($bc * $m)][$i + ($ac * $n)] = 1000000;
                                $unvisited{($v + ($bc * $m)).",".($i + ($ac * $n))} = 1;
                        }
                        }
                }
        }

}


for ($t = 0; $t < $maxy; $t++) {
for ($s = 0; $s < $maxx; $s++) {
        print $map[$s][$t];
}
print "\n";
}



$distance[0][0] = 0;

$x = 0;
$y = 0;

$cnt = 0;
%relevant = (); #Optimization - only scan unvisited neighbours that we have "seen" - thus we don't scan whole map unneccessary.

while (($x != $maxx - 1)||($y != $maxy - 1)) {

        #Implementation of djikstra algoritm.

        if (($unvisited{($x - 1).",".$y} == 1)&&($x > 0)) {
                $relevant{($x - 1).",".$y} = 1;
                if ($distance[$x - 1][$y] > $distance[$x][$y] + $map[$x - 1][$y]) {
                        $distance[$x - 1][$y] = $distance[$x][$y] + $map[$x - 1][$y];
                }
        }
        if (($unvisited{($x + 1).",".$y} == 1)&&($x < $maxx)) {
                $relevant{($x + 1).",".$y} = 1;
                if ($distance[$x + 1][$y] > $distance[$x][$y] + $map[$x + 1][$y]) {
                        $distance[$x + 1][$y] = $distance[$x][$y] + $map[$x + 1][$y];
                }
        }
        if (($unvisited{$x.",".($y - 1)} == 1)&&($y > 0)) {
                $relevant{$x.",".($y - 1)} = 1;
                if ($distance[$x][$y - 1] > $distance[$x][$y] + $map[$x][$y - 1]) {
                        $distance[$x][$y - 1] = $distance[$x][$y] + $map[$x][$y - 1];
                }
        }
        if (($unvisited{$x.",".($y + 1)} == 1)&&($y < $maxy)) {
                $relevant{$x.",".($y + 1)} = 1;
                if ($distance[$x][$y + 1] > $distance[$x][$y] + $map[$x][$y + 1]) {
                        $distance[$x][$y + 1] = $distance[$x][$y] + $map[$x][$y + 1];
                }
        }


        delete($unvisited{$x.",".$y});
        delete($relevant{$x.",".$y});

        $smallestvalue = 1000000;
        foreach $uvn (keys %relevant) {
                ($q, $z) = split(",",$uvn);
                if (($distance[$q][$z] < $smallestvalue)&&($unvisited{$uvn} == 1)) {
                        $smallestvalue = $distance[$q][$z];
                        $x = $q;
                        $y = $z;
                }
        }

        $cnt++;
        if (($cnt / 500) == int($cnt / 500)) {
                print "passed through $cnt iterations\n";
        }
}

$risksum = $distance[$maxx - 1][$maxy - 1];
print $risksum."\n";