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

- 人材獲得作戦・４　試験問題ほか (人生を書き換える者すらいた。)
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 の組み合わせにすると深さ優先探索になります。
まあともかく、二次元で人が認識できるサイズの迷路なら幅優先で十分です。

パイナップルはかなり好きです。
でも丸ごと買ってきて切って食べるという経験はありませんでした。
ある日、帰宅すると玄関にパイナップルがどどーんと鎮座していました。
何日かしてよい感じになってきたそうなので、切ってもらって食べました。
うまうま！



てなわけで、切ってるところを写真メモ（順不同）：



ごちそうさまでした！


photos by :

■Canon デジタル一眼レフカメラ EOS Kiss X2
[楽天で探す]

■Canon EFレンズ 35mm F2
[楽天で探す]

結婚式の二次会とかよく行われている恵比寿のコンツェというビルの6Fのカジュアルイタリアンなお店で新年会でした。
参加者は分類しづらいんだけど、まあアカデミック成分入りなウェブ系な人たち。



TRATTORIA KIORA THE FUOCO (トラットリアキオラザフォーコ)
http://r.gnavi.co.jp/a466112/
http://www.kiora.jp/fouco/
場所：東京都渋谷区恵比寿南2-3-14 CONZE恵比寿6F
電話：03-3715-1830



参加者は全部で16人くらいだったかな。
把握できた Twitter アカウント（順不同、随時追加）:
@oritako, @i2k, @arg, @masaokakihara, @emasha, @rhys_no1

その後、二次会として7人でちょろりでつまみとビール。
餃子は食べたんだけど、チャーハンやラーメンはなし。
それはそれで健全かな。

出雲大社といえば島根県ですが、六本木にもあるのです。



出雲大社東京分祠
http://www.izumotaisya-tokyobunshi.com/main5.htm

出雲大社東京分祠は出雲大社の御祭神大国主神の御分霊を奉斎する都内でも最古の社であり、従って神前結婚式も都内各神社に先んじて明治31年より始めた古い歴史と伝統を有して居りまして当神殿にて挙式相成ることは新郎新婦の幾千代かけて壽ぐ一生一度の御慶事を一層 意義づけることゝ存じます。

コンクリートな建物ですが、ちゃんと神社です。



おみくじをひきましたよ！


絵馬もいっぱいありました。


行ったのは昨年末です。
初詣ではありませんでした。

photos by :

■Canon デジタル一眼レフカメラ EOS Kiss X2
[楽天で探す]

■Canon EFレンズ 35mm F2
[楽天で探す]