幅優先探索 perl版

以下、ソース。

use strict;
my ($start,$goal);
my @value = ();
{
  my $_board =<<"EOD";
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
EOD
  my @rows = split(/\n/,$_board);
  for(my $i=0;$i<@rows;$i++){
    $value[$i] = [];
    my @line = split("",$rows[$i]);
    for(my $j=0;$j<@line;$j++){
      $value[$i][$j] = $line[$j];
      if($line[$j] eq 'S'){
        $start = [$i,$i];
      }elsif($line[$j] eq 'G'){
        $goal = [$i,$j];
      }
    }
  }
}

my @queue = ();
my %route = {};
push @queue,$start;

my @dir = ([0,-1],[1,0],[0,1],[-1,0]);
my $n;
my $flag = 0;
my $c = 0;

while(($n = shift(@queue))){
  last if $flag;
  for(my $i=0;$i<4;$i++){
    my $p = [$n->[0]+$dir[$i][0],$n->[1]+$dir[$i][1]];
    if(!defined $route{join(':',@$p)} and $value[$p->[0]][$p->[1]] ne '*'){
      $route{join(':',@$p)} = join(':',@$n);
      push @queue,$p;
      if(join(':',@$p) eq join(':',@$goal)){
        $flag = 1;
        last;
      }
    }
  }
}
my $p = join(':',@$goal);
my @route = ();
while($p = $route{$p}){
  my @s = split(':',$p);
  $value[$s[0]][$s[1]] = '$';
  if($p eq join(':',@$start)){
    last;
  }
}

for(my $i=0;$i<@value;$i++){
  for(my $j=0;$j<@{$value[$i]};$j++){
    print $value[$i][$j];
  }
  print "\n";
}