#!/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{'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 "  ", $T{'v'}, "\n";
print $T{'b'}[0];
for (my $i=0; $i<9; $i++) {
    print $T{'h'}, $T{'h'}, $T{'b'}[1];
}
print  $T{'h'}, $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, ($i,$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];
}