2023/34.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.38;
   4 use experimental 'multidimensional';
   5 use Array::Heap;
   6 $; = ';';
   7
   8 my @map = map { chomp; [ split // ] } <>;
   9 my $xmax = $#{ $map[0] };
  10 my $ymax = $#map;
  11
  12 my @dx = (1, 0, -1, 0);
  13 my @dy = (0, 1, 0, -1);
  14
  15 my @q;
  16 push_heap @q, [ $xmax + $ymax, 0, 0, 0, 4, [0, 0] ];
  17 my %min_cost;
  18 $min_cost{0,0,0} = 0; # $x, $y, $dir
  19 while (@q) {
  20         my $node = pop_heap @q;
  21         my ($w, $x, $y, $cost, $prevdir, @path) = @$node;
  22
  23         if ($x == $xmax && $y == $ymax) {
  24                 say "$cost : ", join(', ', map { join(',', @$_) } @path);
  25                 last;
  26         }
  27
  28         DIR:
  29         for my $dir (0 .. 3) {
  30                 next if $dir == ($prevdir ^ 2) || $dir == $prevdir;
  31                 my $nx = $x;
  32                 my $ny = $y;
  33                 my $ncost = $cost;
  34                 for (1 .. 10) {
  35                         $nx += $dx[$dir];
  36                         $ny += $dy[$dir];
  37                         next DIR if $nx > $xmax || $ny > $ymax || $nx < 0 || $ny < 0;
  38                         $ncost += $map[$ny][$nx];
  39                         next if $_ < 4;
  40                         next if defined $min_cost{$nx,$ny,$dir}
  41                                 && $min_cost{$nx,$ny,$dir} <= $ncost;
  42                         $min_cost{$nx,$ny,$dir} = $ncost;
  43                         my $nw = ($xmax-$nx) + ($ymax-$ny) + $ncost;
  44                         push_heap @q, [ $nw, $nx, $ny, $ncost, $dir, @path, [$nx, $ny] ];
  45                 }
  46         }
  47 }
  48