迷路に迷う

use strict;
use warnings;

package Local::Maze;

sub new {
	my ($class, $maze) = @_;

	return bless {
		maze => [ map{[ split // ]} split(/^/, $maze) ],
		ans  => [],
	}, $class;
}

sub start {
	my ($self) = @_;

	for(my $y = 0; $y < @{$self->{maze}}; $y++){
		for(my $x = 0; $x < @{$self->{maze}->[$y]}; $x++){
			($self->point($x, $y) eq 'S') or next;
			return ($x, $y);
		}
	}
	die "Not found Start\n";
}

sub point { return $_[0]->{maze}->[$_[2]]->[$_[1]] }
sub set { $_[0]->{maze}->[$_[2]]->[$_[1]] = $_[3] }

sub ans {
	my ($self) = @_;

	foreach(@{$self->{ans}}){
		$self->set(@{$_}, '#');
	}
}

sub draw {
	my ($self) = @_;

	print map{ @{$_} } @{$self->{maze}}
}

package Local::Route;
=begin
辿ったルートを覚えさせるためのクラス。
実態は二次元配列です。別のデータ形式でも実装できるようにクラスにしました。
=cut

sub new {
	my ($class) = @_;

	return bless {
		route => [],
	}, $class;
}

sub set { $_[0]->{route}->[$_[2]]->[$_[1]] = $_[3] }
sub get { return $_[0]->{route}->[$_[2]]->[$_[1]] }


package Local::Maze::BFS;
use base 'Local::Maze';

=begin
点Sから点Gまでの最短路の経路探索の問題なので、グラフを利用します。アルゴリズムは最短路なので幅優先探索を選びました。
http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

アルゴリズム
1. スタートのノードを空のキューに加える
2. ノードをキューの先頭から取り出し、以下の処理を行う
    ・ノードがゴールなら、探索をやめ結果を返す
    ・そうでなければ、ノードに隣接する未探索のノードを全てキューに追加する
3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す
4. 2.に戻る

迷路では「道」がノードで、上下左右の4方向の道を探索します。また、すべての順路を記録し、ゴールについた時点で、ゴールからスタートへ道をたどり回答にします。

アルゴリズムを直感的に言えば、まず一歩で進める場所、次に二歩で進める場所を全て探し、一歩ずつ歩数を増やして行き、n歩でゴールを見つけたら終了です。(n-1)歩まで進める場所を全て探してもゴールが見つからなかったので、n歩が最短距離になり、たどった道順が最短経路(の内の一つ)になります。

アルゴリズムの証明は……T.コルメン、C.ライザーソン、R.リベスト,1995,アルゴリズムイントロダクション第2巻アルゴリズムの設計と解析手法を参照してください。私には無理でしたorz
=cut

sub walk {
	my ($self) = @_;

	my $route = Local::Route->new;
	my @queue;

	my ($sx, $sy) = $self->start;
	$route->set($sx, $sy, [undef, undef]);
	push(@queue, [$sx, $sy, 0]);

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

		foreach([0, -1], [1, 0], [0, 1], [-1, 0]){
			my ($nx, $ny) = ($x+$_->[0], $y+$_->[1]);

			my $p = $self->point($nx, $ny);
			if ($p eq 'G'){
				print "--- Found ", $step+1, "steps.\n";
				$self->_ans($route, $x, $y);
				return;
			}
			if ($p eq '*'){
				next;
			}
			if (defined $route->get($nx, $ny)){
				next;
			}

			$route->set($nx, $ny, [$x, $y]);
			push(@queue, [$nx, $ny, $step+1]);
		}
	}
	die "Not found Goal\n";
}

sub _ans {
	my ($self, $route, $x, $y) = @_;

	my ($px, $py) = ($x, $y);

	my @ans;
	while(defined $px and defined $py){
		push(@ans, [$px, $py]);
		($px, $py) = @{ $route->get($px, $py) };
	}
	$self->{ans} = \@ans;
}

package main;

my $maze_text = <<'EOF';
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
EOF

MAIN: {
	my $maze = Local::Maze::BFS->new($maze_text);
	$maze->walk;
	$maze->ans;
	$maze->draw;
	exit;
}