blob: 90f3e54ea4c2e1c2a247c4dff8bfca7021b1ac3f (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
use strict;
use warnings;
my %edges;
while (<>) {
/(\w+)-(\w+)/;
$edges{$1} //= [];
$edges{$2} //= [];
push @{$edges{$1}}, $2;
push @{$edges{$2}}, $1;
}
my $paths = 0;
my @queue = (['start']);
while (@queue) {
my @path = @{pop @queue};
my %visited = map { $_ => 1 } @path;
for (@{$edges{$path[0]}}) {
if ($_ eq 'end') {
$paths++;
} elsif (/[a-z]/ && $visited{$_}) {
next;
} else {
my @next = ($_, @path);
push @queue, \@next;
}
}
}
print "$paths\n";
$paths = 0;
@queue = (['start']);
while (@queue) {
my @path = @{pop @queue};
my (%visited, $twice);
for (@path) {
$twice = 1 if $visited{$_}++ && /[a-z]/;
}
for (@{$edges{$path[0]}}) {
next if $_ eq 'start';
if ($_ eq 'end') {
$paths++;
} elsif (/[a-z]/ && $visited{$_} && $twice) {
next;
} else {
my @next = ($_, @path);
push @queue, \@next;
}
}
}
print "$paths\n";
|