7 my @map = map { chomp; [ split // ] } <>;
8 my $xmax = $#{$map[0]};
12 if ($xmax == 101 && $ymax == 36) { # too lazy to compute GCD
15 $mod = ($xmax-1) * ($ymax-1);
19 sub occupied($x,$y,$time) {
21 my $nmap = $nmaps[$t];
22 return $nmap->{"$x,$y"}
24 for my $y (0 .. $ymax) {
25 for my $x (0 .. $xmax) {
26 next if ($map[$y][$x] eq '.');
27 my ($nx, $ny) = ($x, $y);
28 if ($map[$y][$x] eq '>') {
29 $nx = 1 + (($x+$t-1) % ($xmax-1));
30 } elsif ($map[$y][$x] eq 'v') {
31 $ny = 1 + (($y+$t-1) % ($ymax-1));
32 } elsif ($map[$y][$x] eq '^') {
33 $ny = 1 + (($y-$t-1) % ($ymax-1));
34 } elsif ($map[$y][$x] eq '<') {
35 $nx = 1 + (($x-$t-1) % ($xmax-1));
37 if ($nmap->{"$nx,$ny"}) {
38 if ($nmap->{"$nx,$ny"} =~ /\d/) {
41 $nmap->{"$nx,$ny"} = 2;
44 $nmap->{"$nx,$ny"} = $map[$y][$x];
49 return $nmap->{"$x,$y"};
52 my @q = [$xmax+$ymax, 1, 0, 0];
55 my $now = pop_heap @q;
56 my ($dist, $x, $y, $time) = @$now;
57 my $key = join(',',$x, $y, ($time % $mod));
58 next if $seen{$key}++;
59 # say "at $x $y dist $dist time $time";
60 if ($x == $xmax-1 && $y == $ymax) {
66 if (!occupied($x,$y,$time)) {
67 push_heap @q, [ $dist, $x, $y, $time ];
69 if (!occupied($x+1,$y,$time)) {
70 push_heap @q, [ $dist-1, $x+1, $y, $time ];
72 if (!occupied($x-1,$y,$time)) {
73 push_heap @q, [ $dist+1, $x-1, $y, $time ];
75 if (!occupied($x,$y+1,$time)) {
76 push_heap @q, [ $dist-1, $x, $y+1, $time ];
78 if ($y > 1 && !occupied($x,$y-1,$time)) {
79 push_heap @q, [ $dist+1, $x, $y-1, $time ];