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-z1-4]/;
15 $pos_of{$c} = [ $x, $y ];
19 my $nkeys = keys %pos_of;
26 my $min_dist = 1_000_000;
33 my ($cost0, $cost, @opened) = @_;
35 my @robots = splice(@opened, 0, 4);
36 my %opened = map { $_ => 1 } @opened;
38 my $key = join('', $robots[0], sort(@robots[1..3]), '|', sort @opened);
40 if (defined $min_cost{$key} && $min_cost{$key} <= $cost) {
44 $min_cost{$key} = $cost;
46 $max_opened = @opened if (!defined $max_opened || @opened > $max_opened);
47 if (!defined $max_cost || $max_cost < $cost) {
49 say "walk $cost - $key ", length $key, ' ', $max_opened;
51 if ($nkeys == @opened) {
57 my $p = $pos_of{$robots[0]};
58 my @q = [ @$p, $cost ];
61 $seen{$p->[0],$p->[1]} = 1;
65 while (my $pos = shift @q) {
66 my ($x, $y, $steps) = @$pos;
70 if ($v =~ /[a-z]/ && !$opened{$v}) {
72 my $cost = $steps + $nkeys - @opened;
73 # say "opened=". scalar @opened;
74 push_heap @q0, [ $cost, $steps, $v, @robots[1..3], $v, @opened ];
75 push_heap @q0, [ $cost, $steps, $robots[1], $v, @robots[2..3], $v, @opened ];
76 push_heap @q0, [ $cost, $steps, $robots[2], $v, @robots[1,3], $v, @opened ];
77 push_heap @q0, [ $cost, $steps, $robots[3], $v, @robots[1..2], $v, @opened ];
80 next if !$opened{lc($v)};
83 for my ($dx, $dy) (1, 0, 0, 1, -1, 0, 0, -1) {
84 my ($nx, $ny) = ($x + $dx, $y + $dy);
85 next if $seen{$nx,$ny}++;
86 push @q, [ $nx, $ny, $steps+1 ];
91 push_heap @q0, [0, 0, 1, 2, 3, 4, 1, 2, 3, 4];
93 my $elem = pop_heap @q0;