Perl深度优先迷宫算法

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Perl›Perl教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　迷宫求解，可以用穷举法，将每个点的方向都穷举完；由于在求解过程中会遇到某一方向不可通过，此时就必须按原路返回。

　　想到用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)