ソースコード

#!/usr/bin/perl

my ($maze);

my ($startX, $startY);  # Start position
my ($mazeSX, $mazeSY);  # Size of maze
sub {
    $mazeSY = 0;
    foreach (<DATA>) {
        $x = 0;
        foreach (split //) {
            ($startX, $startY) = ($x, $mazeSY) if /S/;
            $maze->{$x}->{$mazeSY} = $_;
            $x++;
        }
        $mazeSY++;
    }
    $mazeSX = $x;
}->('Initialize maze field from __DATA__');

my ($goalX, $goalY);    # Goal position
sub {
    $maze->{$startX}->{$startY} = $step = 1;
    while (1) {
        for my $y (0..$mazeSY) {
            for my $x (0..$mazeSX) {
                next if $maze->{$x}->{$y} != $step;
                for (0..3) {
                    my $xx = $x + ( 0,+1, 0,-1)[$_];
                    my $yy = $y + (-1, 0,+1, 0)[$_];
                    $_ = $maze->{$xx}->{$yy};
                    if (/G/) {
                        ($goalX, $goalY) = ($xx, $yy);
                        return; # Finish searching
                    }
                    elsif (/ / || $step < $_) {
                        $maze->{$xx}->{$yy} = $step + 1; # Fill with step count
                    }
                }
            }
        }
        $step++;
    }
}->('Find the shortest route to each point');

sub {
    while ($startX != $goalX || $startY != $goalY) {
        for (0..3) {
            my $xx = $goalX + ( 0,+1, 0,-1)[$_];
            my $yy = $goalY + (-1, 0,+1, 0)[$_];
            if ($maze->{$xx}->{$yy} == $step) {
                $maze->{$xx}->{$yy} = '$';
                ($goalX, $goalY) = ($xx, $yy);
                last;
            }
        }
        $step--;
    }
    $maze->{$startX}->{$startY} = 'S';
}->('Fill the shortest route to goal');

sub {
    for my $y (0..$mazeSY) {
        for my $x (0..$mazeSX) {
            print int $maze->{$x}->{$y} ? ' ' : $maze->{$x}->{$y};
        }
    }
}->('Print maze');

__DATA__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

コードの解説

　処理ごとに関数で括っています。迷路を初期化→各マスまでの最短到達距離を求める→ゴールからスタートまでマーキング→画面に出す、という感じ。アルゴリズムの肝は最短到達距離を求める部分で、A*(エースター)だとか αβ 枝狩りだとか色々テクニックはあるらしいんですが、多分、使っていません。普通にゼロからロジックを考えて実装しました。なので、アルゴリズムを知っている方が有利だとか、というのは多分無い。理論的に考える能力があって、時間をかければ誰でも解ける問題ですね。というわけで、ぐだぐだ言ってる奴はコード書けよハゲ。なかなか面白かった。
　えーっと、話を戻して最短到達距離の求め方は、1) 隣のマスに移動すると歩数+1、2) 既に到達したマスでも、到達距離が今の方が短ければ、その値でアップデート、というルールだけで、これを盤面全体でぐるーっと回してやれば、盤面上の各点に移動するための最短距離が得られます。ゴールに関係なく、盤面全体で処理しているので効率悪いけど。
　グローバル変数と変数の使いまわしはexcuse。