迷路の最短経路を探すプログラムを作成するという問題について。

- 人材獲得作戦・４　試験問題ほか (人生を書き換える者すらいた。)
http://okajima.air-nifty.com/b/2010/01/post-abc6.html

これは単なる幅優先でOKですね。
足跡を記録していき、すでに別の子が通った道にぶつかるか（足跡の有無で判定）、行き止まりに到達したら枝狩り。
幅優先なんだからこれで見つかるのが最短経路。
後からの「最短性のチェック」は不要です。

「アルゴリズム知らないとできない」とか以前の問題で、正式にプログラミングの基礎を学んだ人ならできて当たり前の問題です。ピンと来ない人は、ポインタわからない、再帰わからない人と同列かなあ。

バリバリプログラミングからは一線を退いている私は書くのに30分くらいかかりました。活きのいいヤングなプログラマなら10分くらいで行けるかも。

私の書いたスクリプトです(perl)：

#!/usr/bin/perl
use strict;
use warnings;

my @mm = map {chomp; [split(//, $_)]} <>; # 地図を読んで配列にセット

my ($y, $x); # スタート地点をセット
for (my $ty = 0; $ty < @mm; $ty++) {
    for (my $tx = 0; $tx < @{$mm[$ty]}; $tx++) {
	($y, $x) = ($ty, $tx) if $mm[$ty][$tx] eq 'S';
    }
}

my $path;  # 正解パス
my @ft;	   # 足跡
my @nodes; # 探検隊（複数）
push @nodes, {Y => $y, X => $x, PATH => [[$y, $x]]};
while (@nodes) {
    my $cur = shift @nodes;
    my ($y, $x) = ($cur->{Y}, $cur->{X});
    if ($mm[$y][$x] eq "G") {
	$path = $cur->{PATH};
	last;
    }
    foreach my $d ([0,1], [0,-1], [1,0], [-1,0]) {
	if ($mm[$y+$$d[0]][$x+$$d[1]] =~ /[ G]/ 
	    and not $ft[$y+$$d[0]][$x+$$d[1]]) {
	    push @nodes, {Y => $y+$$d[0], X=> $x+$$d[1],
	        PATH => [@{$cur->{PATH}}, [$y+$$d[0], $x+$$d[1]]]};
	    $ft[$y+$$d[0]][$x+$$d[1]] = 1;
	}
    }
}

foreach my $yx (@{$path}) {
    $mm[$yx->[0]][$yx->[1]] = '$' if $mm[$yx->[0]][$yx->[1]] eq " ";
}
print join("\n", map  {join("", @{$_})} @mm), "\n";

実行例：

 % cat a.map
 **************************
 *S* *                    *
 * * *  *  *************  *
 * *   *    ************  *
 *    *                   *
 ************** ***********
 *                        *
 ** ***********************
 *      *              G  *
 *  *      *********** *  *
 *    *        ******* *  *
 *       *                *
 **************************
 % ./a.pl a.map
 **************************
 *S* * $$$$               *
 *$* *$$* $*************  *
 *$* $$*  $$************  *
 *$$$$*    $$$$$          *
 **************$***********
 * $$$$$$$$$$$$$          *
 **$***********************
 * $$$$$* $$$$$$$$$$$$$G  *
 *  *  $$$$*********** *  *
 *    *        ******* *  *
 *       *                *
 **************************

データ取り込みの簡易化のため、配列へのアクセスはXYではなくYXになっています。
通った足跡を記録する足跡配列は @ft。
通った子供はそこに 1 をセットします。
push と shift の組み合わせで幅優先探索になっていますが、push と pop の組み合わせにすると深さ優先探索になります。
まあともかく、二次元で人が認識できるサイズの迷路なら幅優先で十分です。