Hey, no fair changing the rules in the middle... 

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11114231
use warnings;

my ($startrow, $startcol, $destrow, $destcol);
my @m;
my @visited;
my $maxrow;
my $maxcol;
my $maxscore;
my $minlength;
my $best;

for my $SIZE ( 2, 3 )             # add in 1024 and be prepared to wai
+t :)
  {
# srand 42;                     # uncomment for the specified problem 
+grid
  my $W = $SIZE;
  my $H = $SIZE;
  my $maxscore = 10;
  my $Grid = [];
  for my $row ( 0 .. $H - 1 )
    {
    $Grid->[$row] = [(0)x$W];
    for my $col ( 0 .. $W - 1 )
      {
      $Grid->[$row]->[$col] = $maxscore - int(rand(2*$maxscore+1))
      }
    }
  # now add a highscore to stand out for just 1 cell in each column
  my $highscore = 21;
  for my $row ( 0 .. $H - 1 )
    {
    $Grid->[$row]->[int(rand($W))] = $highscore;
    }

  for my $row ( 0 .. $H-1 )
    {
    printf "%4d" x $W . "\n", @{ $Grid->[$row] };
    }
  print "\n";

  ($startrow, $startcol, $destrow, $destcol) = (0, 0, $H-1, $W-1);
  @m = @$Grid;
  @visited = ();
  $maxrow = $W-1;
  $maxcol = $H-1;
  $maxscore = undef;
  $minlength = undef;
  $best = undef;
  $visited[$startrow][$startcol] = 1;

  try( $startrow, $startcol, $m[$startrow][$startcol] );

  $best or die "no best found";
# print "\n$best\n\n";
  my @best = split ' ', $best;
  my @values;
  print "best path:\n";
  for ( my $i = 0; $i < @best - 4; $i += 3 )
    {
    print directions(@best[$i .. $i+5]), ' ';
#   push @values, $m[$best[$i]][$best[$i+1]];
    push @values, $best[$i+2] eq '00' ? '00' : $m[$best[$i]][$best[$i+
+1]];
    }
  print "\n= ";
  print join '+', @values, $m[$best[-3]][$best[-2]];
  print "\n= $best[-1]\n\n";
  }

sub try
  {
  my ($row, $col, $score) = @_[-3 .. -1];
# print "$row $col $score\n";
  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 )
      {
#     if( $m[$r][$col] >= 0 ||
#       $r == $destrow && $col == $destcol )
        {
        if( $r < $row - 1 )
          {
          my @slide = map {($_, $col, '00') } reverse $r + 1 .. $row -
+ 1;
          try( @_, @slide, $r, $col, $score + $m[$r][$col] );
          }
        elsif( $r > $row + 1 )
          {
          my @slide = map {($_, $col, '00') } $row + 1 .. $r - 1;
          try( @_, @slide, $r, $col, $score + $m[$r][$col] );
          }
        else
          {
          try( @_, $r, $col, $score + $m[$r][$col] );
          }
        }
      }
    --$visited[$r][$col];
    }
  for my $c ( 0 .. $maxcol )
    {
    if( ++$visited[$row][$c] == 1 )
      {
#     if( $m[$row][$c] >= 0 ||
#       $row == $destrow && $c == $destcol )
        {
        if( $c < $col - 1 )
          {
          my @slide = map {($row, $_, '00') } reverse $c + 1 .. $col -
+ 1;
          try( @_, @slide, $row, $c, $score + $m[$row][$c] );
          }
        elsif( $c > $col + 1 )
          {
          my @slide = map {($row, $_, '00') } $col + 1 .. $c - 1;
          try( @_, @slide, $row, $c, $score + $m[$row][$c] );
          }
        else
          {
          try( @_, $row, $c, $score + $m[$row][$c] );
          }
        }
      }
    --$visited[$row][$c];
    }
  }

sub directions
  {
  my ($rowfrom, $colfrom, $fromscore, $rowto, $colto, $toscore) = @_;
  return +($rowfrom != $rowto ?
    $rowfrom < $rowto ? 'down' : 'up' :
    $colfrom < $colto ? 'right' : 'left') .
    ($toscore eq '00' ? '-slide' : '');
  }

[download]

Sample Output: 

  21  -8
   5  21

best path:
down right 
= 21+5+21
= 47

   3  21  -6
   9  21  10
  -7   7  21

best path:
down right-slide right left up down-slide down right 
= 3+9+00+10+21+21+00+7+21
= 92

[download]

For a size of 1024 x 1024, run time is estimated to be either the twelfth of never, or three days after the heat death of the universe, whichever comes last.

In reply to Re^3: Code challenge: Route planning on a 2D grid by tybalt89
in thread Code challenge: Route planning on a 2D grid by bliako

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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! —
  • 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:
    & &amp;
    < &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.