幅優先探索 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"; }