例の話題の試験の解答

とりあえず、ざっくりとこんな感じか。

#!/usr/bin/perl

use strict;
use warnings;

my @map;
my @start;
my @goal;
my $i = 0;
while (<>) {
    chomp;
    my @map_line = split(//, $_);
    my $j = 0;
    foreach (@map_line) {
        @start = ($i, $j) if $_ eq 'S';
        @goal  = ($i, $j) if $_ eq 'G';
        $j++;
    }
    push @map, \@map_line;
    $i++;
}
$map[$start[0]][$start[1]] = ' ';
$map[$goal[0]][$goal[1]] = ' ';

my @queue;

my ($x, $y) = @start;
$map[$x][$y] = 0;
until ($x == $goal[0] and $y == $goal[1]) {
    my $last = 0;
    foreach ([$x-1, $y], [$x+1, $y], [$x, $y-1], [$x, $y+1]) {
        my ($nx, $ny) = @$_;
        if ($map[$nx][$ny] eq ' ') {
            $map[$nx][$ny] = $map[$x][$y] + 1;
            push @queue, $_;
        }
    }

    ($x, $y) = @{shift @queue};
}

($x, $y) = @goal;
until ($x == $start[0] and $y == $start[1]) {
    $map[$x][$y] = '$';
    my $last = 0;
    my ($minx, $miny);
    my $min;
    foreach ([$x-1, $y], [$x+1, $y], [$x, $y-1], [$x, $y+1]) {
        my ($nx, $ny) = @$_;
        if ($map[$nx][$ny] !~ /[\$\* ]/ and (not defined $min or $min > $map[$nx][$ny])) {
            $min = $map[$nx][$ny];
            ($minx, $miny) = @$_;
        }
    }
    ($x, $y) = ($minx, $miny);
}

$map[$start[0]][$start[1]] = 'S';
$map[$goal[0]][$goal[1]] = 'G';
foreach (@map) {
    print join('', map { $_ =~ /[\*\$SG]/ ? $_ : ' ' } @$_) . "\n";
}

結果

mkataigi:~$ cat sample
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
mkataigi:~$ ./route.pl < sample
**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

基本的なダイクストラで実装。

他のことやりながらでしたが、だいたい１時間半位だったかな。