Perlラビリンスソリューション

<?xml version="1.0" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <svg width="112" height="96" version="1.1" xmlns="http://www.w3.org/2000/svg"> <rect width="112" height="96" fill="white" stroke="none" /> <title>5 by 4 orthogonal maze</title> <g fill="none" stroke="#000000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round"> <line x1="16" y1="16" x2="32" y2="16" /> <line x1="48" y1="16" x2="80" y2="16" /> <line x1="16" y1="80" x2="96" y2="80" /> <line x1="16" y1="16" x2="16" y2="80" /> <line x1="96" y1="16" x2="96" y2="80" /> <line x1="64" y1="16" x2="64" y2="32" /> <line x1="32" y1="32" x2="32" y2="48" /> <line x1="32" y1="32" x2="48" y2="32" /> <line x1="64" y1="32" x2="64" y2="48" /> <line x1="64" y1="32" x2="80" y2="32" /> <line x1="32" y1="48" x2="48" y2="48" /> <line x1="48" y1="48" x2="48" y2="64" /> <line x1="48" y1="48" x2="64" y2="48" /> <line x1="80" y1="48" x2="80" y2="64" /> <line x1="16" y1="64" x2="32" y2="64" /> <line x1="48" y1="64" x2="64" y2="64" /> <line x1="80" y1="64" x2="80" y2="80" /> </g> <g fill="black" stroke="none" stroke-width="1"> <text x="24" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">1</text> <text x="40" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">2</text> <text x="56" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">3</text> <text x="72" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">4</text> <text x="88" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">5</text> <text x="24" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">6</text> <text x="40" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">7</text> <text x="56" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">8</text> <text x="72" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">9</text> <text x="88" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">10</text> <text x="24" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">11</text> <text x="40" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">12</text> <text x="56" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">13</text> <text x="72" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">14</text> <text x="88" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">15</text> <text x="24" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">16</text> <text x="40" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">17</text> <text x="56" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">18</text> <text x="72" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">19</text> <text x="88" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">20</text> </g> </svg> 

 @ARGV = ("/PATH/05.svg"); undef $/; $input=(<>); $idx = 1; my $rows; my $cols; # ==================== #   # ==================== while ($input =~ m/<title>([0-9]*)\sby\s([0-9]*).*/g) { ($colCount, $rowCount) = ($1, $2); $rows = $rowCount; $cols = $colCount; print "Rows: $rows Cols: $cols\n"; } my @lines; while ($input =~ m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g) { ($x1,$y1,$x2,$y2) = ($1 / 16,$2 / 16,$3 / 16,$4 / 16); my %H = ( "x1" => $x1, "x2" => $x2, "y1" => $y1, "y2" => $y2 ); #print "#$idx: X1 : ".$H{"x1"}." X2: $x2 Y1: $y1 Y2: $y2\n"; $idx++; #      #if ($y2 > $rows + 1) { $rows = $y2 - 1; } #if ($x2 > $cols + 1) { $cols = $x2 - 1; } #    push @lines, \%H; } # ================================================ #   # HASH[EL + 1][top|right|bot|left] = value; # ================================================ $elCount = $rows * $cols; #     my @elements = (); my @corners = (); for (my $i = 0; $i < $elCount; $i++) { my %H = ( "top" => ($i + 1) - $cols, "right" => ($i + 1) + 1, "bot" => ($i + 1) + $cols, "left" => ($i + 1) - 1, "left_top_x" => 0, "left_top_y" => 0, "right_top_x" => 0, "right_top_y" => 0 ); #    $row = int($i / $cols) + 1; $col = int($i % $cols) + 1; #  if ($H{"top"} > $elCount || $H{"top"} < 1) { $H{"top"} = 0; } if ($H{"right"} > ($row * $cols) || $H{"right"} < 1) { $H{"right"} = 0; } if ($H{"bot"} > $elCount || $H{"bot"} < 1) { $H{"bot"} = 0; } if ($H{"left"} < ((($row - 1)* $cols) + 1) || $H{"left"} < 1) { $H{"left"} = 0; } #print "Row: $row Col: $col\n"; $mult = 1; #print "El: #".($i + 1)." \n"; @corners[$i] = { "left_top_x" => (($col + 0) * $mult), #    "left_top_y" => (($row + 0) * $mult), "right_top_x" => (($col + 1) * $mult), #    "right_top_y" => (($row + 0) * $mult) }; #print "Top: (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 0) * $mult).")\n"; #print "Bot: (".(($col + 0) * $mult).",".(($row + 1) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n"; #print "Right: (".(($col + 1) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 1) * $mult).",".(($row + 1) * $mult).")\n"; #print "Left: (".(($col + 0) * $mult).",".(($row + 0) * $mult).") -> (".(($col + 0) * $mult).",".(($row + 1) * $mult).")\n"; foreach (@lines) { #print "(".$_->{"x1"}.",".$_->{"y1"}.") -> (".$_->{"x2"}.",".$_->{"y2"}.")\n"; #   if ($_->{"y1"} == (($row + 0) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) { # print "No Top Neighbour: ".($i + 1)."\n"; undef $H{"top"}; } #   if ($_->{"y1"} == (($row + 1) * $mult) && (($col + 0) * $mult) >= $_->{"x1"} && (($col + 1) * $mult) <= $_->{"x2"}) { # print "No Bot Neighbour: ".($i + 1)."\n"; undef $H{"bot"}; } #   if ($_->{"x1"} == (($col + 1) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) { # print "No Right Neighbour: ".($i + 1)."\n"; undef $H{"right"}; } #   if ($_->{"x1"} == (($col + 0) * $mult) && (($row + 0) * $mult) >= $_->{"y1"} && (($row + 1) * $mult) <= $_->{"y2"}) { # print "No Left Neighbour: ".($i + 1)."\n"; undef $H{"left"}; } } # print ($i + 1); # print ":"; # print "\t".$H{"top"} if defined $H{"top"}; # print "\t".$H{"right"} if defined $H{"right"}; # print "\t".$H{"bot"} if defined $H{"bot"}; # print "\t".$H{"left"} if defined $H{"left"}; push @{$elements[$i]}, $H{"top"} if defined $H{"top"}; push @{$elements[$i]}, $H{"right"} if defined $H{"right"}; push @{$elements[$i]}, $H{"bot"} if defined $H{"bot"}; push @{$elements[$i]}, $H{"left"} if defined $H{"left"}; print "".($i + 1).":\t"; foreach (@{$elements[$i]}) { print $_."\t"; } print "\n"; } # ================================================ #   # ================================================ my $start; my $end; my $newElement; my $oldElement; my @solution; # 1.     print "     \n"; for ($i = 0; $i < scalar @elements; $i++) { for ($j = 0; $j < scalar @{$elements[$i]}; $j++) { if ($start && @{$elements[$i]}[$j] == 0) { print "End = ".($i + 1)."\n"; $end = $i; last; } if (!$start && @{$elements[$i]}[$j] == 0) { print "Start = ".($i + 1)."\n"; $start = $i; } } } # 2.   my $discovered = (); #  discovered ()  false (  - ) print "#Nodes: ".(scalar @elements)."\n\n"; for ($i = 0; $i < scalar @elements; $i++) { $discovered[$i] = 0; } #     DFS($start); sub DFS { my ($i) = @_; #   –  ,  ,    if (($i + 1) == ($end + 1)) { #    –      true push @solution, ($i + 1); $discovered[$i] = 1; return 1; } elsif ($discovered[($_ - 1)] == 1) { #   -  false return 0; } else { #   #print "Node: ".($i + 1)."\n"; $discovered[$i] = 1; #    #   true,     foreach (@{$elements[$i]}) { #print "Neighbour: ".($_)."\n"; #   0,  false –    ! if ($_ != 0) { $result = DFS($_ - 1); if ($result == 1) { push @solution, $_; return 1; } } } #    return 0; } } #    push @solution, ($start + 1); # =============================================================== #  #     solutionStack # =============================================================== print "\nStack: "; foreach (@solution) { print "$_ "; } print "\n"; print "<g fill=\"none\" stroke=\"#FF0000\" stroke-width=\"3\" stroke-linecap=\"round\" stroke-linejoin=\"round\">"; for ($i = 0; $i < scalar @solution; $i++) { $x = ((($corners[$solution[$i] - 1]{"right_top_x"} + $corners[$solution[$i] - 1]{"left_top_x"}) / 2) * 16); $y = ((($corners[$solution[$i] - 1]{"right_top_y"} + $corners[$solution[$i] - 1]{"left_top_y"}) / 2) * 16) + 8; if (($i + 1) < scalar @solution) { $x2 = ((($corners[$solution[$i + 1] - 1]{"right_top_x"} + $corners[$solution[$i + 1] - 1]{"left_top_x"}) / 2) * 16); $y2 = ((($corners[$solution[$i + 1] - 1]{"right_top_y"} + $corners[$solution[$i + 1] - 1]{"left_top_y"}) / 2) * 16) + 8; } print "<line x1=\"$x\" y1=\"$y\" x2=\"$x2\" y2=\"$y2\" />\n"; } print "</g>\n"; # # print "Found Solution!";