4 use experimental 'multidimensional';
8 my @map = map { chomp; [ split // ] } <>;
9 my $xmax = $#{ $map[0] };
12 my @dx = (1, 0, -1, 0);
13 my @dy = (0, 1, 0, -1);
16 push_heap @q, [ $xmax + $ymax, 0, 0, 0, 0, 0, [0, 0] ];
18 $min_cost{0,0,0,0} = 0; # $x, $y, $dir, $dist
21 my $node = pop_heap @q;
22 my ($w, $x, $y, $cost, $prevdir, $dist, @path) = @$node;
24 if ($x == $xmax && $y == $ymax) {
25 say "$cost : ", join(', ', map { join(',', @$_) } @path);
29 for my $dir (0 .. 3) {
30 next if $dir == ($prevdir ^ 2);
32 my $nx = $x + $dx[$dir];
33 my $ny = $y + $dy[$dir];
34 next if $nx > $xmax || $ny > $ymax || $nx < 0 || $ny < 0;
36 my $ndist = ($dir == $prevdir) ? $dist+1 : 1;
39 my $ncost = $cost + $map[$ny][$nx];
40 next if defined $min_cost{$nx,$ny,$dir,$ndist}
41 && $min_cost{$nx,$ny,$dir,$ndist} <= $ncost;
42 $min_cost{$nx,$ny,$dir,$ndist} = $ncost;
43 my $nw = ($xmax-$nx) + ($ymax-$ny) + $ncost;
44 push_heap @q, [ $nw, $nx, $ny, $ncost, $dir, $ndist, @path, [$nx, $ny] ];