OK, distance of sliding squares does not count. But when on a slide, the starting and ending square of one segment (segment=1 line, no turnings) counts. right?

I also thought whether moving backwards is allowed. That can change the problem's nature, so I suggest either no back movement or two flavours, one with back movements and one without.

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.

Your output for the 3x3 grid looks weird

Neither do cells with 00 appear nor is it possible to go right after a right-slide.

Could it be that you coded slides as a one cell no move with weight 00?

Update:

Ok this Re^7: Code challenge: Route planning on a 2D grid makes it clearer.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

> no fair changing the rules

Which rules do you apply?

> For a size of 1024 x 1024, run time is estimated to be either the twelfth of never,

Depends on the rules.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

I understood the OP like all turning points have to be counted.

I'd define the length of a path by number of necessary moves. Hence length is 0 if start and end are identical. (This facilitates adding partial solutions)

I think allowing back-moves is necessary to "solve" a 1024 x 1024 grid with an approach based on probability.

Compare this Re: Highest total sum path problem

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

> OK, distance of sliding squares does not count.

I hope it's obvious now that this makes it pretty much

O(n**2)

with

n = length = #rows= #columns

because the number of optimal solutions is "bigger" than eternity.

Counting the distance of slides makes this far more complicated, such that you should change the challenge to "best solution so far" instead of "optimal solution".

It's also important to understand that optimal sum is easy, shortest (Hamilton) path is problematic.

My approach would be a two dimensional divide and conquer.

Like for n=1024=2**10 solving 32 smaller grids with n=32=2**5 side length.

One could also divide further to 5 stages since 4**5=1024.

The basic idea is still probabilistic.

Because of your randomization there is a probability of roughly .5 that a cell is positive.

Hence two neighboring cells (minimal distance) have the probability of .25 to be both positive.

This means that if you need to find a minimal transit between two areas with m neighboring cells, then the there is a 1-0.75**m to find it.

Hence finding very good solutions is not that difficult.

It's the optimal solution which is on another page.

But in terms of a coding challenge this should be a big plus, because the crowd loves rankings and hates math. ;)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

just have fun or as Tuco said in The Good, the Bad and the Ugly: When you have to shoot, shoot. Don't talk.