18.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4
   5 my @m = map { chomp; [ split // ]; } <>;
   6 my $maxy = $#m;
   7 my $maxx = $#{$m[0]};
   8
   9 my @basins;
  10 my $max_id = 0;
  11 my @prev_row;
  12 for my $row (@m) {
  13         my $prev_l = undef;
  14         for my $i (0 .. $#$row) {
  15                 my $b_id;
  16                 if ($row->[$i] == 9) {
  17                         $b_id = undef;
  18                 } elsif (!$prev_l && !$prev_row[$i]) {
  19                         $b_id = ++$max_id;
  20                 } elsif (!$prev_l) {
  21                         $b_id = $prev_row[$i];
  22                 } elsif (!$prev_row[$i] || $prev_l == $prev_row[$i]) {
  23                         $b_id = $prev_l;
  24                 } else { # merge
  25                         $b_id = $prev_row[$i];
  26                         $basins[$b_id] += $basins[$prev_l];
  27                         $basins[$prev_l] = undef;
  28                         for my $j (0 .. $#$row) {
  29                                 next if !$row->[$j] || $row->[$j] != $prev_l;
  30                                 $row->[$j] = $b_id;
  31                         }
  32                         for my $j (0 .. $#$row) {
  33                                 next if !$prev_row[$j] || $prev_row[$j] != $prev_l;
  34                                 $prev_row[$j] = $b_id;
  35                         }
  36                 }
  37                 $prev_l = $b_id;
  38                 $row->[$i] = $b_id;
  39                 $basins[$b_id]++ if defined $b_id;
  40         }
  41         @prev_row = @$row;
  42 }
  43
  44 @basins = sort { $b <=> $a } grep { defined $_ } @basins;
  45
  46 say $basins[0]*$basins[1]*$basins[2];
  47
  48
  49