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

my (@wall, $start, $end, $width);
my $size = 0;
while (<>) {
	chomp;
	$width //= length;
	for (split //) {
		$wall[$size] = 0 + /#/;
		$start = $size if /S/;
		$end = $size if /E/;
		$size++;
	}
}

my @directions = (0, -$width, 1, $width, -1);
my %compass; @compass{@directions} = qw(any north east south west);
my %arrows; @arrows{@directions} = qw(+ ^ > v <);

my ($any, $north, $east, $south, $west) = @directions;
my %left; @left{@directions} = ($any, $west, $north, $east, $south);
my %right; @right{values %left} = keys %left;
my ($towards, $away_from) = (1, -1);

my @best;
my @best_way = ($any) x $size;
my @found_facing = (0) x $size;

say best_path_score();



# Find best path through maze using an augmented flood-fill, flooding
# from both endpoints. Fill proceeds in order of cost. Minimum total
# cost will be found where the two floods meet.

sub best_path_score {
	my @queue = ((0, $start, $towards, $east), (0, $end, $away_from, $any));
	while (@queue) {
		my ($score, $pos, $facing, $moving) = splice @queue, 0, 4;
		#show($pos, "$score $pos $facing $compass{$moving} / " . join(' ', @queue));

		if (defined $best[$pos]) {
			next if $found_facing[$pos] == $facing;
			next unless $best_way[$pos] == $facing * $moving;
			return $score + $best[$pos];
		}
	
		$best[$pos] = $score;
		$found_facing[$pos] = $facing;
		$best_way[$pos] = $facing * $moving;

		for my $dir ($north, $east, $south, $west) {
			next if $dir == -$moving;
			next if $wall[$pos + $dir];
			
			my $cost = $score + 1;
			$cost += 1000 if $moving && $moving != $dir;

			my $into = 0;
			$into += 4 while $into < @queue && $queue[$into] <= $cost;
			splice @queue, $into, 0, ($cost, $pos + $dir, $facing, $dir);
		}	
	}
}



sub show {
	my $marker = shift;
	my $buffer = '';
	for my $pos (0 .. $#wall) {
		$buffer .=
			$marker == $pos? ' [@@] ':
			defined($best[$pos])? sprintf(
				'%s%04d%s',
			       	$found_facing[$pos] < 0? '-': '+',
			       	$best[$pos],
			       	$arrows{$best_way[$pos]}
			):
			$wall[$pos]? '######':
			'  ::  ';
		$buffer .= "\n" unless ++$pos % $width;
	}
	say shift if @_;
	say $buffer;
}