#!/usr/bin/perl -w

use strict;
use v5.30;

my @ducts;
my %duct_pos;
my @map;
while (<>) {
	chomp;
	push @map, [ split // ];
	my $line = $_;
	while ($line =~ /\d/g) {
		my $x = pos($line) - 1;
		my $y = $#map;
		$ducts[$&] = [ $x, $y ];
		$duct_pos{$x,$y} = $&;
		say "$& at ", pos($line)-1, ",$#map";
	}
}

my $xmax = $#{ $map[0] };
my $ymax = $#map;
$; = ',';

my %dist;

sub walk {
	my ($duct) = @_;
	
	my ($x, $y) = @{ $ducts[$duct] };
	my @q = ([ $x, $y, 0 ]);
	my %seen = ("$x,$y" => 1);
	my $ducts_seen = 0;
	while (@q) {
		my $entry = shift @q;
		my ($x, $y, $dist) = @$entry;
		if ($map[$y][$x] =~ /\d/) {
			$dist{$duct}{$&} = $dist;
			say "dist $duct -> $& = $dist";
			return if (++$ducts_seen >= @ducts);
		}
		for ([0, 1], [0, -1], [1, 0], [-1, 0]) {
			my $dx = $x + $_->[0];
			my $dy = $y + $_->[1];
			next if $dx < 0 || $dx > $xmax || $dy < 0 || $dy > $ymax
				|| $map[$y][$x] eq '#';
			next if $seen{$dx,$dy}++;
			push @q, [ $dx, $dy, $dist+1];
		}
	}
}

walk($_) for 0 .. 7;

my $min_dist;

sub perm {
	my ($dist, $now, @rest) = @_;
	if (!@rest) {
		$min_dist = $dist if !defined $min_dist || $dist < $min_dist;
	}
	for my $i (0 .. $#rest) {
		my @nr = @rest;
		my $duct = splice @nr, $i, 1;
		perm($dist + $dist{$now}{$duct}, $duct, @nr);
	}
}

perm(0, 0 .. 7);

say $min_dist;
