[勉強][プログラミング][perl]幅優先探索 perl版 もういっちょ書いてみた
今度はファイルを読み込んで迷路を解く。
処理もちょっと変えてある。
use strict; use warnings; my $m = Maze->new(); $m->load('maze.txt'); $m->solve(); package Point; use strict; use warnings; sub new{ my ($class,$y,$x,$value) = @_; my $self = bless {},$class; $self->{p} = [$x,$y]; $self->{x} = $x; $self->{y} = $y; $self->{string} = "$y:$x"; $self->{value} = $value; return $self; } package Maze; use strict; use warnings; use Path::Class; sub new{ my ($class) = @_; bless {},$class; } sub load{ my ($self,$fname) = @_; my $map = file($fname)->slurp(); my @rows = split(/\n/,$map); $self->{height} = @rows; $self->{width} = length($rows[0]); $self->{map} = {}; for(my $i=0;$i<@rows;$i++){ my @cols = split('',$rows[$i]); for(my $j=0;$j<@cols;$j++){ $self->{map}{"$i:$j"} = Point->new($i,$j,$cols[$j]); if($cols[$j] eq 'S'){ $self->{start} = $self->{map}{"$i:$j"}; }elsif($cols[$j] eq 'G'){ $self->{goal} = $self->{map}{"$i:$j"}; } } } } sub solve{ my ($self) = @_; my (@queue,%route) = ((),()); my $move = sub{ my @move = @_; return sub{ my ($p,$i) = @_; return $self->{map}{($p->{y}+$move[$i][0]).':'.($p->{x}+$move[$i][1])}; }; }; $move = $move->([0,1],[0,-1],[1,0],[-1,0]); my $flag = 0; my $k = 0; push @queue,$self->{start}; while((my $n = shift @queue)){ last if $flag; for(my $i=0;$i<4;$i++){ my $p = $move->($n,$i); if(!defined $route{$p->{string}} and $p->{value} ne '*'){ $route{$p->{string}} = $n; push @queue,$p; if($p->{string} eq $self->{goal}{string}){ $flag = 1; last; } } } } my $r = $self->{goal}; warn $r->{string}; while(($r = $route{$r->{string}})){ last if $r->{string} eq $self->{start}{string}; warn $r->{string}; $self->{map}{$r->{string}}{value} = '$'; } for(my $i=0;$i<$self->{height};$i++){ for(my $j=0;$j<$self->{width};$j++){ print $self->{map}{"$i:$j"}{value}; } print "\n"; } }