#!/usr/bin/perl -w use Data::Dumper; my $moves = [ [ qw/1UL -1 -2/ ], [ qw/2UR 1 -2/ ], [ qw/3R 2 0/ ], [ qw/4LR 1 2/ ], [ qw/5LL -1 2/ ], [ qw/6L -2 0/ ], ]; my $N = int(); my $line = ; chomp $line; my ( $y_start, $x_start, $y_end, $x_end ) = split /\s+/, $line; my $matrix = { "$x_start,$y_start" => [0,""], # path length, path_algorithm }; my $new_cells = { "$x_start,$y_start" => 1, }; my $current_length = 0; while ( 1 ) { $current_length++; $new_cells = do_step( $new_cells, $matrix, $moves, $current_length ); # print Dumper($new_cells); # for ( sort { $a cmp $b } keys %$new_cells ) { # print join("\t", $_, $matrix->{$_}->[1]) . "\n"; # } # print "\n\n\n"; #print Dumper($matrix); #last if $current_length > 40; # exit; if ( exists($matrix->{"$x_end,$y_end"}) ) { my ( $path_length, $path_str ) = @{$matrix->{"$x_end,$y_end"}}; $path_str =~ s/\d//g; $path_str =~ s/^\s+//g; print join("\n", $path_length, $path_str); exit(0); } if ( scalar(keys %$new_cells) == 0 ) { print "Impossible\n"; exit(0); } } exit(0); sub do_step { my ( $new_cells, $matrix, $moves, $current_length ) = @_; my $res = {}; for my $new_cell ( keys %$new_cells ) { my ( $current_x, $current_y ) = split /\,/, $new_cell; my $matrix_path = $matrix->{"$current_x,$current_y"}->[1]; for my $one_move ( @$moves ) { my ( $move_name, $dx, $dy ) = @$one_move; my ( $cx, $cy ) = ( $current_x + $dx, $current_y + $dy ); if ( $cx >= 0 && $cx < $N && $cy >= 0 && $cy < $N ) { # good_coordinate my $current_path = $matrix_path . " " . $move_name; if ( !exists($matrix->{"$cx,$cy"}) ) { #completely new cell # set matrix $matrix->{"$cx,$cy"} = [ $current_length, $current_path ]; $res->{"$cx,$cy"} = 1; } else { # get matrix length my ( $c_length, $c_path ) = @{ $matrix->{"$cx,$cy"} }; if ( $current_length <= $c_length && $current_path le $c_path ) { $matrix->{"$cx,$cy"} = [ $current_length, $current_path ]; } } } } } return $res; }