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

my $width = 72;
my $size = $width * 71;
my @exits = ([0, 0, 'S'], [0, $size - 2, 'E']);

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

while (<>) {
	$wall[$1 + $width * $2] = 1 if /(\d+),(\d+)/;

	# 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;
		}
	}

	if ($origin[$pos] eq $from) {
		#Floods completed without meeting, no path exists now
		say;
		last;
	}
}