Maybe (or maybe not) slight cheating :)
#!/usr/bin/perl
use strict; # https://perlmonks.org/?node_id=11113757
use warnings;
$_ = <<END;
1 4 5 -1 9
0 3 0 17 -3
1 10 3 0 3
-8 -3 2 1 -4
0 8 4 0 0
END
my $destrow = 2;
my $destcol = 1;
my $startrow = 4;
my $startcol = 4;
my @m = map [split], split /\n/;
my @visited;
my $maxrow = $#m;
my $maxcol = $#{ $m[0] };
my $maxscore;
my $minlength;
my $best;
$visited[$startrow][$startcol] = 1;
try( $startrow, $startcol, 0 );
my @best = split ' ', $best;
my @values;
print "best path:\n";
for ( my $i = 0; $i < @best - 4; $i += 3 )
{
print directions(@best[$i, $i+1, $i+3, $i+4]), ' ';
push @values, $m[$best[$i]][$best[$i+1]];
}
print "\n= ";
print join '+', @values, $m[$best[-3]][$best[-2]];
print "\n= $best[-1]\n";
sub try
{
my ($row, $col, $score) = @_[-3 .. -1];
if( $row == $destrow && $col == $destcol )
{
if( $maxscore )
{
if( $score > $maxscore or
$score == $maxscore and $minlength > @_)
{
$maxscore = $score;
$minlength = @_;
$best = "@_";
}
}
else
{
$maxscore = $score;
$minlength = @_;
$best = "@_";
}
return;
}
for my $r ( 0 .. $maxrow )
{
if( ++$visited[$r][$col] == 1 )
{
$m[$r][$col] > 0 and
try( @_, $r, $col, $score + $m[$r][$col] );
}
--$visited[$r][$col];
}
for my $c ( 0 .. $maxcol )
{
if( ++$visited[$row][$c] == 1 )
{
$m[$row][$c] > 0 and
try( @_, $row, $c, $score + $m[$row][$c] );
}
--$visited[$row][$c];
}
}
sub directions
{
my ($rowfrom, $colfrom, $rowto, $colto) = @_;
if( $rowfrom != $rowto )
{
return +($rowfrom < $rowto ? 'down' : 'up') .
(abs($rowfrom - $rowto) > 1 ? '-slide' : '');
}
else
{
return +($colfrom < $colto ? 'right' : 'left') .
(abs($colfrom - $colto) > 1 ? '-slide' : '');
}
}
Outputs:
best path:
up-slide down-slide left-slide up-slide right down right-slide down-sl
+ide left up-slide down-slide down-slide left up-slide
= 0+9+3+1+1+4+3+17+1+2+5+3+4+8+10
= 71
"real matrix is 50000*50000" HaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHa