Perl解決走迷宮問題

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

#!/usr/bin/perl

#
# Useage: maze.pl
#
#

use strict;
use warnings;

### main program

my @maze;

# maze structure 0->empty 1->wall
# initialize
for ( my $i = 0; $i <= 8; $i++ ) {
    for ( my $j = 0; $j <= 9; $j++ ) {
        $maze[$i][$j][0] = 0;
        $maze[$i][$j][1] = 0;
    }
}

$maze[0][1][0] = 1;
$maze[0][3][0] = 1;
$maze[0][3][1] = 1;
$maze[0][4][1] = 1;
$maze[0][5][1] = 1;
$maze[0][6][0] = 1;
$maze[0][8][0] = 1;
$maze[0][8][1] = 1;
$maze[0][9][1] = 1;

$maze[1][0][0] = 1;
$maze[1][0][1] = 1;
$maze[1][1][1] = 1;
$maze[1][2][1] = 1;
$maze[1][3][1] = 1;
$maze[1][4][0] = 1;
$maze[1][5][0] = 1;
$maze[1][7][0] = 1;
$maze[1][8][0] = 1;
$maze[1][9][0] = 1;
$maze[1][9][1] = 1;

$maze[2][0][1] = 1;
$maze[2][2][0] = 1;
$maze[2][3][0] = 1;
$maze[2][3][1] = 1;
$maze[2][4][0] = 1;
$maze[2][5][1] = 1;
$maze[2][7][0] = 1;
$maze[2][8][0] = 1;
$maze[2][9][0] = 1;
$maze[2][9][1] = 1;

$maze[3][0][1] = 1;
$maze[3][2][0] = 1;
$maze[3][2][1] = 1;
$maze[3][3][1] = 1;
$maze[3][4][1] = 1;
$maze[3][6][0] = 1;
$maze[3][7][0] = 1;
$maze[3][8][0] = 1;
$maze[3][9][0] = 1;
$maze[3][9][1] = 1;

$maze[4][0][0] = 1;
$maze[4][1][1] = 1;
$maze[4][2][1] = 1;
$maze[4][3][1] = 1;
$maze[4][4][0] = 1;
$maze[4][5][0] = 1;
$maze[4][9][1] = 1;

$maze[5][0][1] = 1;
$maze[5][2][0] = 1;
$maze[5][3][0] = 1;
$maze[5][6][1] = 1;
$maze[5][7][1] = 1;
$maze[5][8][0] = 1;
$maze[5][8][1] = 1;
$maze[5][9][1] = 1;

$maze[6][1][1] = 1;
$maze[6][2][0] = 1;
$maze[6][4][1] = 1;
$maze[6][5][1] = 1;
$maze[6][6][0] = 1;
$maze[6][6][1] = 1;
$maze[6][7][1] = 1;
$maze[6][8][0] = 1;
$maze[6][9][1] = 1;

$maze[7][0][1] = 1;
$maze[7][1][0] = 1;
$maze[7][1][1] = 1;
$maze[7][3][1] = 1;
$maze[7][4][1] = 1;
$maze[7][5][0] = 1;
$maze[7][5][1] = 1;
$maze[7][7][1] = 1;

$maze[8][1][1] = 1;
$maze[8][2][1] = 1;
$maze[8][3][1] = 1;
$maze[8][5][1] = 1;
$maze[8][6][1] = 1;
$maze[8][7][0] = 1;
$maze[8][7][1] = 1;
$maze[8][8][1] = 1;
$maze[8][9][1] = 1;

my %T = (
    0 => [ qw(┌ ─ ┐) ],t => [ qw(┌ ┬ ┐) ],m => [ qw(├ ┼ ┤) ],b => [ qw(└ ┴ ┘) ],h => '─',v => '│'
);

#output the maze
# the first line
print $T{'0'}[0];
for (my $i = 0; $i<9; $i++) {
   print $T{'0'}[1],$T{'0'}[1],$T{'t'}[1];
}
print $T{'0'}[1],$T{'t'}[2],"n";
# crosses
for (my $i = 0; $i<9; $i++) {
    print $T{'v'};
    for (my $j =0; $j<9; $j++) {
        print "  ";
        if ($maze[$i][$j][1] == 1) {
            print $T{'v'};
        } else {
            print " ";
        }
    }
    print "  ",$T{'v'},"n";
    print $T{'m'}[0];
    for (my $j =0; $j<9; $j++) {
        if ($maze[$i][$j][0] == 1) {
            print $T{'h'},$T{'h'};
        } else {
            print "  ";
        }
        print $T{'m'}[1];
    }
    if ($maze[$i][9][0] == 1) {
        print $T{'h'},$T{'h'};
    } else {
        print "  ";
    }
    print $T{'m'}[2],"n";
}
# the last row
print $T{'v'};
for (my $i=0; $i<9; $i++) {
    print "  ";
    if ($maze[$i][9][1] == 1) {
        print $T{'v'};
    } else {
        print " ";
    }
}
print "  ","n";
print $T{'b'}[0];
for (my $i=0; $i<9; $i++) {
    print $T{'h'},$T{'h'},$T{'b'}[1];
}
print  $T{'h'},$T{'b'}[2],"n";


# find the path
my @bq=(4,9);       # start position
my @path;           # store the path information
my $i;
my $j;
my $x = 5;
my $y = 0;
for ( my $i = 0; $i <= 9; $i++ ) {
    for ( my $j = 0; $j <= 9; $j++ ) {
        $path[$i][$j][1] = 0;
        $path[$i][$j][2] = 0;
    }
}
while (($#bq + 1) != 0) {
    $i = shift @bq;
    $j = shift @bq;
    $maze[$i][$j][2] = 1;       # already visited node
    if ($i != 0 and $maze[$i-1][$j][0] == 0 and $maze[$i-1][$j][2] == 0) {
        push @bq,($i-1,$j);
        $path[$i-1][$j][0] = $i;
        $path[$i-1][$j][1] = $j;
    }
    if ($j != 0 and $maze[$i][$j-1][1] == 0 and $maze[$i][$j-1][2] == 0) {
        push @bq,($i,$j-1);
        $path[$i][$j-1][0] = $i;
        $path[$i][$j-1][1] = $j;
    }
    if ($i != 9 and $maze[$i][$j][0] == 0 and $maze[$i+1][$j][2] == 0) {
        push @bq,($i+1,$j);
        $path[$i+1][$j][0] = $i;
        $path[$i+1][$j][1] = $j;
    }
    if ($j != 9 and $maze[$i][$j][1] == 0 and $maze[$i][$j+1][2] == 0) {
        push @bq,$j+1);
        $path[$i][$j+1][0] = $i;
        $path[$i][$j+1][1] = $j;
    }
}

# Output the result
$i = $path[5][0][0];
$j = $path[5][0][1];
while ($i != 4 || $j != 9) {
    print "i=",$i,",j=",$j,"n";
    $i = $path[$i][$j][0];
    $j = $path[$i][$j][1];
}

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!