#!/usr/bin/perl -w

use v5.36;
use Data::Dumper;
use Array::Heap;
use feature 'multidimensional';

my @map = map { chomp; [ split // ] } <>;

my %pos_of;
for my $y (0 .. $#map) {
	for my $x (0 .. $#{ $map[0]}) {
		my $c = $map[$y][$x];
		next if $c !~ /[a-z@]/;
		$pos_of{$c} = [ $x, $y ];
	}
}

my $nkeys = keys %pos_of;
say "nkeys = $nkeys";

$; = ';';

my $best;

my $min_dist = 1_000_000;

my %min_cost;
my @q0;
sub walk {
	my ($cost, @opened) = @_;

	my %opened = map { $_ => 1 } @opened;

	my $key = $opened[0] . join('', sort @opened);

	if (defined $min_cost{$key} && $min_cost{$key} <= $cost) {
		return;
	}

	$min_cost{$key} = $cost;

	say "walk $min_dist $cost - $key ", length $key;
	if ($nkeys + 1 == length $key) {
		say "Found!";
		exit 1;
	}

	my $p = $pos_of{$opened[0]};
	my @q = [ @$p, $cost ];

	my %seen;
	$seen{$p->[0],$p->[1]} = 1;

	my %dist;

	while (my $pos = shift @q) {
		my ($x, $y, $steps) = @$pos;

		my $v = $map[$y][$x];
		next if $v eq '#';
		if ($v =~ /[a-z]/ && !$opened{$v}) {
			$dist{$v} //= $steps;
			# say "opened=". scalar @opened;
			$min_dist = $steps if $min_dist > $steps
				&& @opened == keys %pos_of;
			push_heap @q0, [ $steps, $v, @opened ];
		}
		if ($v =~ /[A-Z]/) {
			next if !$opened{lc($v)};
		}
	
		for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) {
			my ($nx, $ny) = ($x + $dx, $y + $dy);
			next if $seen{$nx,$ny}++;
			push @q, [ $nx, $ny, $steps+1 ]
				if $steps + 1 < $min_dist;
		}
	}
}

push_heap @q0, [0, '@'];
while (@q0) {
	my $elem = pop_heap @q0;
	walk(@$elem);
}

say $min_dist;
