#!/usr/bin/perl
use v5.35.0;

my $width = 72;
my $size = $width * 71;

my (@wall, @exits);
for (my $i = $width - 1; $i < $size; $i += $width) {
	$wall[$i] = 1;
}

my $max = 1024;
while (<>) {
	$wall[$1 + $width * $2] = 1 if /(\d+),(\d+)/;
	last unless --$max;
}

push @exits, [0, 0, 'S'], [0, $size - 2, 'E'];

# Flood-fill the map, starting simultaneously from all exits and working in
# strict cost order, to work out lowest cost to escape (lcte) for all tiles.

my @lcte;

# Don't actually need to flood the whole thing, just enough to find the first
# place where the flood spreading from the S exit meets one spreading from
# the E exit. That will be on a a path of least cost to both S and E, and
# therefore a path of least cost across the whole maze.
#
# To make detecting flood meetings possible, we need to keep track of where
# any given tile was flooded from.

my @origin = ('') x $size;

my ($cost, $pos, $from);
my @queue = @exits;
while (@queue) {
	($cost, $pos, $from) = @{shift @queue};

	if (defined $lcte[$pos]) {
		# Detect flood meeting point
		last if ($origin[$pos] || $from) ne $from;
		# but don't otherwise reprocess already-seen tiles
		next;
	}

	# Tile is newly flooded - record that
	$lcte[$pos] = $cost;
	$origin[$pos] = $from;

	# and flood its neighbours
	for my $step (-$width, 1, $width, -1) {
		my $next = $pos - $step;
		push @queue, [$cost+1, $next, $from] unless
			$next < 0 || $next >= $size ||
		       	$wall[$next] || $origin[$next] eq $from;
	}
}

my $path_length = $cost + $lcte[$pos];

say	"Via tile $pos: ",
	"$cost from $from, ",
	"$lcte[$pos] from $origin[$pos], ",
	"total $path_length";



sub guts {
	return '-' unless @_;
	if (@_ == 1) {
		my $arg = $_[0] // 'und';
		my $ref = ref($arg);
		if ($ref eq 'ARRAY') {
			return '['.join(' ', map {guts($_)} @$arg).']';
		} elsif ($ref eq 'HASH') {
			return '{'.join(' ', map {$_.'=>'.guts($$arg{$_})} sort keys %$arg).'}';
		} else {
			return $arg;
		}
	}
	return '(' . join(' ', map {guts($_)} @_) . ')';
}



sub show {
	say shift while @_;
	for (my $row = 0; $row < $size; $row += $width) {
		my $line = sprintf '%5d ', $row;
		for (my $pos = $row; $pos < $row + $width; ++$pos) {
			if ($wall[$pos]) {$line .= '#'}
			elsif ($origin[$pos]) {$line .= $origin[$pos]}
			else {$line .= '.'}
		}
		say $line;
	}
	say '';
}