Perl深度优先迷宫算法
迷宫求解，可以用穷举法，将每个点的方向都穷举完；由于在求解过程中会遇到某一方向不可通过，此时就必须按原路返回。想到用Perl数组来保存路径，记录每次所探索的方向，方便原路返回时得到上一步的方向，再退回到可以通过的方向，继续探索，直到终点或者最终无法到达，正常退出程序为止。
求解过程的关键思想：
1、由于需要标记下一位置是否已探索，需要一个数组用来记录每个点是否可通过；
定义如：0--未经过 1--已走 2--不可通过
2、原路返回需要知道回退到哪个点，那么每一步要记录当前坐标；
3、采用深度优先搜索路径，每一步需记录搜索方向；
采用HASH表：{ coordinate=> , direct=>'UP' }
4、用数组保存每一步，数组下标即代表当前步
关键算法：
北上，撞墙后原路返回，取出数组末元素，判断方向是否已搜索；已搜索完毕，继续原路返回；未搜索完，进行下个方向搜索，当前点放到数组尾。
循环。
5、算法伪码：
do{
if(当前点未经过){
设置已走
将当前位置的坐标、方向保存
if(当前点为终点){
修改迷宫的数据，记录所走的路线
return 1
}
当前步增一
新的坐标点=当前坐标＋移动方向
}
else{ # 当前位置走不通
if(数组非空){
取出当前步
while(当前位置所走方向已搜索 && 数组非空){
记录当前位置不可通过
取出上一步状态
原路返回
}
if(当前的位置搜索方向小于4){
当前位置的方向增一
数组重新记录当前步数
新的坐标点=当前坐标＋移动方向
}
}
}
}while(数组非空)
初始化迷宫：
初始化标记数组: 2、不可通过 0、未经过
路径：从蛇头到蛇尾
代码如下：
use strict;
use constant {WIDTH=>12,HEIGHT=>8,DEBUG=>1,};
my %uldr=(1=>[-1,0],
2=>,
3=>,
4=>,);# 上、左、下、右
my @bg=();
for(my $y=0;$y<HEIGHT;$y++){
for( my $x=0 ; $x<WIDTH ; $x++ ){
if( $y == 0 || $y == HEIGHT-1 ||
$x == 0 || $x == WIDTH-1){
$bg[$y][$x] = '*';
}
else{
$bg[$y][$x] = ' ';
}
}
}# 初始化迷宫
my @tmp=( ,,,,,,, );# 障碍物坐标
map{ $bg[ $tmp[$_] ][ $tmp[$_] ] = '#' } 1..$#tmp-1;
$bg[ $tmp ][ $tmp ] = '@';
print @$_,"\n" foreach(@bg);
my @bg_ghost=map{ [ split('','0'x (WIDTH)) ] }0..(HEIGHT-1);# 0--未经过 1--已走 2--不可通过
map{ my $y=$_;map { $bg_ghost[$y][$_] = ( $bg[$y][$_] eq '#' || $bg[$y][$_] eq '*')?2:0 }0..$#{$bg} }0..$#bg;# 障碍物设置不可通过
print @$_,"\n" foreach(@bg_ghost);
print "-"x15,"\n";
sub handle{
my @path=();# 存放步数的数组
my $cur_position=[ $tmp , $tmp ];# 起点
my $end=[ $tmp[-1] , $tmp[-1] ];# 终点
my ($step,$p_step)=(0,'');# 步数、指向数组元素的指针
do{
if($bg_ghost[ $cur_position-> ][ $cur_position-> ] == 0 ){# 当前位置未经过
$bg_ghost[ $cur_position-> ][ $cur_position-> ]=1;# 设置当前位置已走
$path[$step]={step=>$step,
coordinate=>[$cur_position->,$cur_position->],
direct=>1,
};# 保存当前位置信息：坐标、方向
print "path[$step]:$path[$step]:",$path[$step]->{step},"\n" if DEBUG;
print " (y,x):(",$cur_position->,",",$cur_position->,")\n" if DEBUG;
if( $cur_position->==$end-> && $cur_position->==$end->){
my @arr=('A'..'Z','a'..'z');
foreach(0..$#path){
$bg[ $path[$_]->{coordinate}-> ][ $path[$_]->{coordinate}-> ] = $arr[$_];
}
return 1;
}
$step++;
$cur_position=[ $path[$step-1]->{coordinate}->+$uldr{1}->,
$path[$step-1]->{coordinate}->+$uldr{1}-> ];
}
else{# 当前位置已走/不可通过
if(@path){
$p_step=pop(@path);# 取出当前步
while($p_step->{direct}==4 && (@path)){# 4个方向已经搜索完
$bg_ghost[ $p_step->{coordinate}-> ][ $p_step->{coordinate}-> ] = 2;# 设置不可通过
$p_step=pop(@path);# 上一步状态
$step--;# 上一步编号
}
if($p_step->{direct}<4){
$p_step->{direct}++;
print " step:",scalar(@path)," p_step->{direct}:",$p_step->{direct},"\n" if DEBUG;
push @path,$p_step;
my @temp=@{$p_step->{coordinate}};
$cur_position = [ $temp+$uldr{$p_step->{direct}}->,
$temp+$uldr{$p_step->{direct}}-> ];
print " (y,x):(",$cur_position->,",",$cur_position->,")\n" if DEBUG;
}
}
}
}while(@path);
return 0;
}
my $x=&handle;
print @$_,"\n" foreach(@bg);
运行信息如下：
path:HASH(0x1585174):0
(y,x):(1,5)
step:0 p_step->{direct}:2
(y,x):(1,4)
step:0 p_step->{direct}:3
(y,x):(2,5)
path:HASH(0x15849f4):1
(y,x):(2,5)
step:1 p_step->{direct}:2
(y,x):(2,4)
path:HASH(0x1584a14):2
(y,x):(2,4)
step:2 p_step->{direct}:2
(y,x):(2,3)
step:2 p_step->{direct}:3
(y,x):(3,4)
path:HASH(0x1584954):3
(y,x):(3,4)
step:3 p_step->{direct}:2
(y,x):(3,3)
step:3 p_step->{direct}:3
(y,x):(4,4)
path:HASH(0x1584924):4
(y,x):(4,4)
step:4 p_step->{direct}:2
(y,x):(4,3)
path:HASH(0x1584884):5
(y,x):(4,3)
step:5 p_step->{direct}:2
(y,x):(4,2)
path:HASH(0x158479c):6
(y,x):(4,2)
step:6 p_step->{direct}:2
(y,x):(4,1)
path:HASH(0x158471c):7
(y,x):(4,1)
path:HASH(0x158463c):8
(y,x):(3,1)
View Code
页:
[1]