#!/usr/bin/perl use strict; use warnings; my $dirs = { UL => [-2, -1], UR => [-2, 1], R => [0, 2], LR => [2, 1], LL => [2, -1], L => [0, -2], }; my $i = 0; my @order = qw(UL UR R LR LL L); my $seq = { '' => scalar @order, map { $_ => $i++ } @order }; sub printShortestPath { my ($n, $i_start, $j_start, $i_end, $j_end) = @_; my ($dist, $prev, $path) = dijkstra(@_); my @S; my $u = [$i_end, $j_end]; while (ref $u && defined $prev->[$u->[0]][$u->[1]]) { unshift @S, $path->[$u->[0]][$u->[1]]; $u = $prev->[$u->[0]][$u->[1]]; } # print "result:\n"; # gprint(@$_) foreach $dist, $prev, $path; print scalar @S, "\n", join(' ', @S), "\n" if @S; print "Impossible\n" if ! @S; } sub dijkstra { my ($n, $i_start, $j_start, $i_end, $j_end) = @_; my (@Q, @dist, @prev, @path, @removed); foreach my $i (0..$n-1) { foreach my $j (0..$n-1) { $dist[$i][$j] = $n+1; $prev[$i][$j] = undef; $path[$i][$j] = undef; # push @Q, [$i, $j]; } } @Q = ([$i_start, $j_start]); # priority queue style $dist[$i_start][$j_start] = 0; # $prev[$i_start][$j_start] = 0; # $path[$i_start][$j_start] = 0; # print "dist0:\n"; # gprint(@dist); # @Q = sort { # $dist[$a->[0]][$a->[1]] <=> $dist[$b->[0]][$b->[1]] # || $seq->{$path[$a->[0]][$a->[1]] || ''} <=> $seq->{$path[$b->[0]][$b->[1]] || ''} # } @Q; while (my $u = shift @Q) { # print 'on: ', join ', ', @$u, "\n"; $removed[$u->[0]][$u->[1]]++; return \@dist, \@prev, \@path if $u->[0] == $i_end && $u->[1] == $j_end; foreach my $dir (@order) { my $v = [$u->[0] + $dirs->{$dir}->[0], $u->[1] + $dirs->{$dir}->[1]]; # out of bounds next if $v->[0] < 0 || $v->[0] >= $n; next if $v->[1] < 0 || $v->[1] >= $n; # already visited next if $removed[$v->[0]][$v->[1]]; my $alt = $dist[$u->[0]][$u->[1]] + 1; # new tentative distance # print "$dir to @$v distance = $alt\n"; if ($alt < $dist[$v->[0]][$v->[1]]) { # better than current distance # print "$dir is shorter\n"; $dist[$v->[0]][$v->[1]] = $alt; # update tables $prev[$v->[0]][$v->[1]] = $u; $path[$v->[0]][$v->[1]] = $dir; push @Q, $v; } } # print "dist:\n"; # gprint(@dist); @Q = sort { $dist[$a->[0]][$a->[1]] <=> $dist[$b->[0]][$b->[1]] || $seq->{$path[$a->[0]][$a->[1]] || ''} <=> $seq->{$path[$b->[0]][$b->[1]] || ''} } @Q; } } sub gprint { my @matrix = @_; foreach my $row (@matrix) { printf "%5s ", ref $_ ? join ',', @$_ : $_ // '-' foreach @$row; print "\n"; } print "\n"; } my $n = ; chomp $n; my $i_start_temp = ; my @i_start_arr = split / /,$i_start_temp; my $i_start = $i_start_arr[0]; chomp $i_start; my $j_start = $i_start_arr[1]; chomp $j_start; my $i_end = $i_start_arr[2]; chomp $i_end; my $j_end = $i_start_arr[3]; chomp $j_end; printShortestPath($n, $i_start, $j_start, $i_end, $j_end);