6 use feature 'multidimensional';
8 my @map = map { chomp; [ split // ] } <>;
11 for my $y (0 .. $#map) {
12 for my $x (0 .. $#{ $map[0]}) {
14 next if $c !~ /[a-z@]/;
15 $pos_of{$c} = [ $x, $y ];
19 my $nkeys = keys %pos_of;
26 my $min_dist = 1_000_000;
31 my ($cost, @opened) = @_;
33 my %opened = map { $_ => 1 } @opened;
35 my $key = $opened[0] . join('', sort @opened);
37 if (defined $min_cost{$key} && $min_cost{$key} <= $cost) {
41 $min_cost{$key} = $cost;
43 say "walk $min_dist $cost - $key ", length $key;
44 if ($nkeys + 1 == length $key) {
49 my $p = $pos_of{$opened[0]};
50 my @q = [ @$p, $cost ];
53 $seen{$p->[0],$p->[1]} = 1;
57 while (my $pos = shift @q) {
58 my ($x, $y, $steps) = @$pos;
62 if ($v =~ /[a-z]/ && !$opened{$v}) {
64 # say "opened=". scalar @opened;
65 $min_dist = $steps if $min_dist > $steps
66 && @opened == keys %pos_of;
67 push_heap @q0, [ $steps, $v, @opened ];
70 next if !$opened{lc($v)};
73 for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) {
74 my ($nx, $ny) = ($x + $dx, $y + $dy);
75 next if $seen{$nx,$ny}++;
76 push @q, [ $nx, $ny, $steps+1 ]
77 if $steps + 1 < $min_dist;
82 push_heap @q0, [0, '@'];
84 my $elem = pop_heap @q0;