user
Your latest contract has hit a snag. You came to update the army payroll system, but awoke this morning to the sound of mortars landing not far away and panicked generals banging on you door. The President has loaded his gold on trucks and needs to find the shortest route to safety. You are given the following map. The top left hand corner is (0,0). You and The President are located at HQ in the centre of the country (11,11). Cells marked 0 indicate safety. Numbers other than 0 indicate the number of cells that his party will travel in a day in any direction up, down, left, right, or diagonally.

```
         00000         
      00003130000      
    000321322221000    
   00231222432132200   
  0041433223233211100  
  0232231612142618530  
 003152122326114121200 
 031252235216111132210 
 022211246332311115210 
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
 013322444412122123210 
 015132331312411123120 
 003333612214233913300 
  0219126511415312570  
  0021321524341325100  
   00211415413523200   
    000122111322000    
      00001120000      
         00000         

```

Part 1 Use Dijkstra's algorithm to find a list of the shortest routes from HQ to safety.
  
Part 2  
Six days later and you are called to another briefing. The good news is The President and his gold are safe, so your invoice may be paid if you can get out of here. To do this a number of troop repositions will be required. It is concluded that you need to know the shortest route from each cell to every other cell. You decide to use Floyd's algorithm. Print the shortest route from (21,11) to (1,11) and from (1,11) to (21,11), and the longest shortest route between any two points.
  
Extra Credit

1. Is there any cell in the country that can not be reached from HQ?
2. Which cells will it take longest to send reinforcements to from HQ?

Related tasks:

1. Dijkstra's algorithm
2. Floyd-Warshall algorithm

See also

* Back from the Klondike.
assistant
**Translation of**: Perl

```
my $d = qq:to/END/;
         00000
      00003130000
    000321322221000
   00231222432132200
  0041433223233211100
  0232231612142618530
 003152122326114121200
 031252235216111132210
 022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
 013322444412122123210
 015132331312411123120
 003333612214233913300
  0219126511415312570
  0021321524341325100
   00211415413523200
    000122111322000
      00001120000
         00000
END

my $w = $d.split("\n")».chars.max;
$d = $d.split("\n")».fmt("%-{$w}s").join("\n"); # pad lines to same length
$w++;

my @directions = ( 1, -1, -$w-1, -$w, -$w+1, $w-1, $w, $w+1);
my @nodes.push: .pos - 1 for $d ~~ m:g/\d/;
my %dist = @nodes.race.map: { $_ => all-destinations([$_]) };

sub all-destinations (@queue) {
    my %to;
    my $dd = $d;
    while shift @queue -> $path {
        my $from = ($path.split(' '))[*-1];
        my $steps = $dd.substr($from, 1);
        next if $steps eq ' ';
        %to{$from} //= $path;
        next if $steps eq '0';
        $dd.substr-rw($from, 1) = '0';
        for @directions -> $dir {
            my $next = $from + $steps × $dir;
            next if $next < 0 or $next > $dd.chars;
            @queue.push: "$path $next" if $dd.substr($next, 1) ~~ /\d/;
        }
    }
    %to;
}

sub   to-xy ($nodes) { join ' ', $nodes.split(' ').map: { '(' ~ join(',', floor($_/$w), $_%$w) ~ ')' } }
sub from-xy ($x, $y) { $x × $w + $y }

my $startpos = from-xy 11, 11;

my %routes;
%routes{.split(' ').elems}.push: .&to-xy
    for grep { .so }, map { %dist{$startpos}{$_} }, grep { '0' eq $d.substr($_, 1) }, @nodes;
my $n = %routes{ my $short-route = %routes.keys.sort.first }.elems;
say "Shortest escape routes ($n) of length {$short-route - 1}:\n\t" ~
    %routes{$short-route}.join("\n\t");

say "\nShortest from (21,11) to  (1,11):\n\t" ~ %dist{from-xy 21, 11}{from-xy  1, 11}.&to-xy;
say "\nShortest from  (1,11) to (21,11):\n\t" ~ %dist{from-xy  1, 11}{from-xy 21, 11}.&to-xy;

my @long-short = reverse sort { .split(' ').elems }, gather %dist.deepmap(*.take);
my $l = @long-short[0].split(' ').elems;
say "\nLongest 'shortest' paths (length {$l-1}):";
say "\t" ~ .&to-xy for grep { .split(' ').elems == $l }, @long-short;

say "\nNot reachable from HQ:\n\t" ~ @nodes.grep({not %dist{$startpos}{$_}}).&to-xy;

my @HQ;
@HQ[.split(' ').elems].push: .&to-xy for %dist{$startpos}.values;
say "\nLongest reinforcement from HQ is {@HQ - 2} for:\n\t" ~ @HQ[*-1].join("\n\t");

```

Output:

```
Shortest escape routes (40) of length 4:
    (11,11) (11,12) (8,12) (6,12) (0,12)
    (11,11) (10,11) (7,11) (7,12) (1,6)
    (11,11) (11,12) (8,9) (2,9) (1,8)
    (11,11) (11,12) (8,9) (2,9) (1,9)
    (11,11) (10,10) (8,10) (5,13) (1,13)
    (11,11) (11,12) (8,9) (2,15) (1,14)
    (11,11) (11,12) (8,9) (2,15) (1,15)
    (11,11) (11,12) (8,9) (2,15) (1,16)
    (11,11) (10,10) (8,10) (5,7) (2,4)
    (11,11) (10,11) (7,8) (7,5) (2,5)
    (11,11) (11,12) (8,9) (2,15) (2,16)
    (11,11) (11,12) (11,9) (9,9) (3,3)
    (11,11) (10,11) (7,8) (4,5) (3,4)
    (11,11) (12,11) (12,14) (8,18) (3,18)
    (11,11) (12,11) (9,14) (6,17) (4,19)
    (11,11) (11,12) (8,9) (8,3) (6,1)
    (11,11) (10,10) (8,8) (8,4) (6,2)
    (11,11) (11,12) (11,15) (11,17) (7,21)
    (11,11) (11,12) (8,9) (8,3) (8,1)
    (11,11) (10,10) (8,8) (12,4) (9,1)
    (11,11) (11,12) (8,9) (14,3) (11,0)
    (11,11) (10,11) (7,8) (7,5) (12,0)
    (11,11) (12,10) (13,10) (13,5) (13,0)
    (11,11) (10,10) (12,8) (16,4) (13,1)
    (11,11) (12,11) (12,14) (16,18) (13,21)
    (11,11) (10,10) (8,8) (12,4) (15,1)
    (11,11) (11,12) (11,15) (11,17) (15,21)
    (11,11) (10,10) (12,8) (16,4) (16,1)
    (11,11) (10,11) (10,14) (12,16) (16,20)
    (11,11) (12,11) (12,14) (16,18) (16,21)
    (11,11) (12,11) (15,8) (15,5) (18,2)
    (11,11) (10,11) (13,8) (14,7) (18,3)
    (11,11) (11,12) (14,9) (18,5) (19,4)
    (11,11) (11,12) (14,15) (16,15) (19,18)
    (11,11) (11,12) (14,12) (16,12) (20,16)
    (11,11) (10,11) (13,11) (17,15) (20,18)
    (11,11) (12,10) (13,10) (18,15) (21,15)
    (11,11) (11,12) (14,9) (18,13) (22,9)
    (11,11) (12,11) (15,8) (18,11) (22,11)
    (11,11) (11,12) (14,9) (18,13) (22,13)

Shortest from (21,11) to  (1,11):
    (21,11) (21,12) (19,10) (14,10) (10,10) (8,8) (4,8) (1,11)

Shortest from  (1,11) to (21,11):
    (1,11) (2,10) (5,13) (9,9) (15,3) (20,8) (20,10) (21,11)

Longest 'shortest' paths (length 9):
    (7,3) (7,4) (5,4) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
    (10,21) (10,20) (9,19) (9,16) (9,9) (15,3) (15,8) (15,5) (15,2) (14,2)
    (11,21) (11,20) (11,16) (11,17) (11,13) (13,11) (17,7) (15,5) (15,2) (14,2)
    (12,21) (12,19) (12,17) (12,16) (12,12) (12,11) (15,8) (15,5) (15,2) (14,2)
    (1,11) (1,12) (4,9) (6,9) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
    (2,9) (2,10) (5,7) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
    (2,13) (2,15) (3,15) (6,12) (12,18) (13,19) (13,20) (17,16) (18,16) (20,14)

Not reachable from HQ:
    (2,18) (4,3) (18,20)

Longest reinforcement from HQ is 6 for:
    (11,11) (11,12) (11,15) (11,17) (7,17) (7,20) (6,20)
    (11,11) (11,12) (11,15) (13,17) (13,19) (13,20) (17,20)
    (11,11) (11,12) (14,12) (16,12) (20,12) (21,11) (22,12)
    (11,11) (11,12) (14,15) (16,17) (17,16) (18,16) (20,14)
    (11,11) (12,11) (9,14) (6,17) (4,17) (4,18) (3,19)
```