#!/usr/bin/perl -w

use strict;
use v5.30;

$_ = <>; # header
$_ = <>; # header
$; = ',';

my (%dead);
my ($xmax, $ymax);
my ($fx, $fy);
while (<>) {
	my ($x, $y, $size, $used) = m|/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T|;
	die "no match at $_" if !defined $used;
	if ($size > 100) {
		$dead{$x,$y} = 1;
	} elsif ($used == 0) {
		$fx = $x;
		$fy = $y;
	}
	$xmax = $x if !$xmax || $xmax < $x;
	$ymax = $y if !$ymax || $ymax < $y;
}

use Array::Heap;
my @q = ( [ $xmax + $xmax-$fx + $fy, $xmax, 0, $fx, $fy, 0 ] );

my %seen;
while (@q) {
	my $state = pop_heap @q;
	my ($score, $gx, $gy, $fx, $fy, $steps) = @$state;
	say "score $score, goal at $gx,$gy, free at $fx,$fy, steps $steps";
	last if $gx == 0 && $gy == 0;
	for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
		my ($dx, $dy) = ($fx + $_->[0], $fy + $_->[1]);
		next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax;
		next if $dead{$dx,$dy};
		my ($ngx, $ngy) = ($gx, $gy);
		if ($dx == $gx && $dy == $gy) {
			($ngx, $ngy) = ($fx, $fy);
		}
		next if $seen{$ngx,$ngy,$dx,$dy}++;
		my $nscore = $ngx+$ngy+abs($dx-$ngx)+abs($dy-$ngy);
		push_heap @q, [ $nscore,
			$ngx, $ngy, $dx, $dy, $steps+1 ];
		say "    F->$dx,$dy $nscore";
	}
}
