#!/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' : '');
    }
  }

##</code><code>##

best path:
up-slide down-slide left-slide up-slide right down right-slide down-slide 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