#!/usr/bin/perl -w

use v5.38;
use experimental 'multidimensional';
use Array::Heap;
$; = ';';

my @map = map { chomp; [ split // ] } <>;
my $xmax = $#{ $map[0] };
my $ymax = $#map;

my @dx = (1, 0, -1, 0);
my @dy = (0, 1, 0, -1);

my @q;
push_heap @q, [ $xmax + $ymax, 0, 0, 0, 4, [0, 0] ];
my %min_cost;
$min_cost{0,0,0} = 0; # $x, $y, $dir
while (@q) {
	my $node = pop_heap @q;
	my ($w, $x, $y, $cost, $prevdir, @path) = @$node;

	if ($x == $xmax && $y == $ymax) {
		say "$cost : ", join(', ', map { join(',', @$_) } @path);
		last;
	}

	DIR:
	for my $dir (0 .. 3) {
		next if $dir == ($prevdir ^ 2) || $dir == $prevdir;
		my $nx = $x;
		my $ny = $y;
		my $ncost = $cost;
		for (1 .. 10) {
			$nx += $dx[$dir];
			$ny += $dy[$dir];
			next DIR if $nx > $xmax || $ny > $ymax || $nx < 0 || $ny < 0;
			$ncost += $map[$ny][$nx];
			next if $_ < 4;
			next if defined $min_cost{$nx,$ny,$dir}
				&& $min_cost{$nx,$ny,$dir} <= $ncost;
			$min_cost{$nx,$ny,$dir} = $ncost;
			my $nw = ($xmax-$nx) + ($ymax-$ny) + $ncost;
			push_heap @q, [ $nw, $nx, $ny, $ncost, $dir, @path, [$nx, $ny] ];
		}
	}
}

