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' : '');
    }
  }
[download]

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
[download]

"real matrix is 50000*50000" HaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHa

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.