Perl深度优先迷宫算法

vlei

　　迷宫求解，可以用穷举法，将每个点的方向都穷举完；由于在求解过程中会遇到某一方向不可通过，此时就必须按原路返回。
　　想到用Perl数组来保存路径，记录每次所探索的方向，方便原路返回时得到上一步的方向，再退回到可以通过的方向，继续探索，直到终点或者最终无法到达，正常退出程序为止。
　　求解过程的关键思想：
1、由于需要标记下一位置是否已探索，需要一个数组用来记录每个点是否可通过；
　　定义如：0--未经过 1--已走 2--不可通过
　　2、原路返回需要知道回退到哪个点，那么每一步要记录当前坐标；
　　3、采用深度优先搜索路径，每一步需记录搜索方向；
　　采用HASH表：{ coordinate=>[y,x] , 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=>[0,-1],
3=>[1,0],
4=>[0,1],);  # 上、左、下、右
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=( [1,5],[1,4],[1,3],[2,3],[3,3],[3,2],[3,1], );  # 障碍物坐标
map{ $bg[ $tmp[$_][0] ][ $tmp[$_][1] ] = '#' } 1..$#tmp-1;
$bg[ $tmp[0][0] ][ $tmp[0][1] ] = '@';
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]} }0..$#bg;  # 障碍物设置不可通过
print @$_,"\n" foreach(@bg_ghost);
print "-"x15,"\n";
sub handle{
my @path=();  # 存放步数的数组
my $cur_position=[ $tmp[0][0] , $tmp[0][1] ];  # 起点
my $end=[ $tmp[-1][0] , $tmp[-1][1] ];  # 终点
my ($step,$p_step)=(0,'');  # 步数、指向数组元素的指针
do{
if($bg_ghost[ $cur_position->[0] ][ $cur_position->[1] ] == 0 ){  # 当前位置未经过
$bg_ghost[ $cur_position->[0] ][ $cur_position->[1] ]=1;  # 设置当前位置已走
$path[$step]={step=>$step,
coordinate=>[$cur_position->[0],$cur_position->[1]],
direct=>1,
};  # 保存当前位置信息：坐标、方向
print "path[$step]:$path[$step]:",$path[$step]->{step},"\n" if DEBUG;
print "    (y,x):(",$cur_position->[0],",",$cur_position->[1],")\n" if DEBUG;
if( $cur_position->[0]==$end->[0] && $cur_position->[1]==$end->[1]){
my @arr=('A'..'Z','a'..'z');
foreach(0..$#path){
$bg[ $path[$_]->{coordinate}->[0] ][ $path[$_]->{coordinate}->[1] ] = $arr[$_];
}
return 1;
}
$step++;
$cur_position=[ $path[$step-1]->{coordinate}->[0]+$uldr{1}->[0],
$path[$step-1]->{coordinate}->[1]+$uldr{1}->[1] ];
}
else{  # 当前位置已走/不可通过
if(@path){
$p_step=pop(@path);  # 取出当前步
while($p_step->{direct}==4 && (@path)){  # 4个方向已经搜索完
$bg_ghost[ $p_step->{coordinate}->[0] ][ $p_step->{coordinate}->[1] ] = 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}}[0,1];
$cur_position = [ $temp[0]+$uldr{$p_step->{direct}}->[0],
$temp[1]+$uldr{$p_step->{direct}}->[1] ];
print "    (y,x):(",$cur_position->[0],",",$cur_position->[1],")\n" if DEBUG;
}
}
}
}while(@path);
return 0;
}
my $x=&handle;
print @$_,"\n" foreach(@bg);
　　
　　运行信息如下：





path[0]: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[1]:HASH(0x15849f4):1
(y,x):(2,5)
step:1 p_step->{direct}:2
(y,x):(2,4)
path[2]: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[3]: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[4]:HASH(0x1584924):4
(y,x):(4,4)
step:4 p_step->{direct}:2
(y,x):(4,3)
path[5]:HASH(0x1584884):5
(y,x):(4,3)
step:5 p_step->{direct}:2
(y,x):(4,2)
path[6]:HASH(0x158479c):6
(y,x):(4,2)
step:6 p_step->{direct}:2
(y,x):(4,1)
path[7]:HASH(0x158471c):7
(y,x):(4,1)
path[8]:HASH(0x158463c):8
(y,x):(3,1)
View Code