14 my ($x, $y, $size, $used) = m|/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T|;
15 die "no match at $_" if !defined $used;
18 } elsif ($used == 0) {
22 $xmax = $x if !$xmax || $xmax < $x;
23 $ymax = $y if !$ymax || $ymax < $y;
27 my @q = ( [ $xmax + $xmax-$fx + $fy, $xmax, 0, $fx, $fy, 0 ] );
31 my $state = pop_heap @q;
32 my ($score, $gx, $gy, $fx, $fy, $steps) = @$state;
33 say "score $score, goal at $gx,$gy, free at $fx,$fy, steps $steps";
34 last if $gx == 0 && $gy == 0;
35 for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
36 my ($dx, $dy) = ($fx + $_->[0], $fy + $_->[1]);
37 next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax;
38 next if $dead{$dx,$dy};
39 my ($ngx, $ngy) = ($gx, $gy);
40 if ($dx == $gx && $dy == $gy) {
41 ($ngx, $ngy) = ($fx, $fy);
43 next if $seen{$ngx,$ngy,$dx,$dy}++;
44 my $nscore = $ngx+$ngy+abs($dx-$ngx)+abs($dy-$ngy);
45 push_heap @q, [ $nscore,
46 $ngx, $ngy, $dx, $dy, $steps+1 ];
47 say " F->$dx,$dy $nscore";