迷路を読む
迷路はさまざまな形式で表現できます。 この場合、SVGを使用してソリューションを簡単に描画できるため、SVGを使用します。
SVGの迷路の例：
<?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>
ファイルを2つのレギュラーで処理します-1つはサイズ用で、もう1つは行を見つけるためです。
サイズ：
m/<title>([0-9]*)\sby\s([0-9]*).*/g
行：
m/<line x1=\"([0-9]+)\" y1=\"([0-9]+)\" x2=\"([0-9]+)\" y2=\"([0-9]+)\" \/>+/g
行を格納する構造にデータを渡しましょう。これは次のようになります。
{ "x1" => 0, "y1" => 0, "x2" => 0, "y2" => 0 }
svgファイルでは、すべてのデータは16の係数に基づいています。したがって、xとyを16で除算し、増加するシーケンスを取得します。
ファイルで最後に行うことは、行と列の数を保存することです。 これは、レギュラーシーズンから取得した最初のグループになります。
隣人のリストを作成します
開始する前に最後にやることは、隣人のリストを作成することです。 これは、目的の要素に隣接するすべての要素のリストです。
上記の迷路のリスト出力：
1: 2 6 2: 0 3 1 3: 8 2 4: 5 5: 0 10 4 6: 1 11 7: 8 8: 3 7 9: 10 14 10: 5 15 9 11: 6 12 12: 17 11 13: 14 14: 9 19 13 15: 10 20 16: 17 17: 12 18 16 18: 19 17 19: 14 18 20: 15
これは簡単なことではありません。隣人を遮断する「壁」の線を考慮する必要があります。 これを行うには、最初にすべての隣人を見つけます。 到達できないものは-1としてマークされます。 その他は正数で示されます。
次に、すべての行を並べ替え、接続していない隣人を除外します。 最後に、配列内のすべての隣接ノードをリストし、上記のように出力します。
ネイバーのリストを受け取ったら、アルゴリズムの使用を開始します。
深さ検索
グラフを使用すると、各ノードを通過してノードを反復処理できます。 それらを3つのカテゴリに分けましょう。
-黒-ノットが見つかりました
-グレー-見つかったが処理されていない
-白-見つかりません
次に、ランダムノードから始めて、すべての隣接ノードを回ります。 各隣接ノードを検出済みとしてマークし、すべてのノードをソートするまでこれらの手順を繰り返します。
擬似コードでは、次のようになります。
// discovered = array(); // for (i = 0; i < discovered.size(); i++) discovered[i] = false; // endIdx = someEndIndex; start_node_idx = someStartNodeIndex; DFS(start_node_idx); // void DFS(nodeIdx) { if (nodeIdx == endIdx) { // – true discovered[nodeIdx] = true; return true; } else if (discovered[nodeIdx]) { // , false return false; } else { // discovered[nodeIdx] = true; foreach (neighbour i of nodeIdx) { result = DFS(i); if (result) { return true; // , } } return false; // , } }
決定の結論
これが最も簡単な手順です。 各セルの中心（左上+ rightbot2）を見つけて線を引きます。
上記すべてのコード
@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!";
出力をsvgファイルに追加する必要があります。
<g fill="none" stroke="#FF0000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round"><line x1="88" y1="24" x2="88" y2="24" /> <line x1="88" y1="24" x2="88" y2="40" /> <line x1="88" y1="40" x2="72" y2="40" /> <line x1="72" y1="40" x2="72" y2="56" /> <line x1="72" y1="56" x2="72" y2="72" /> <line x1="72" y1="72" x2="56" y2="72" /> <line x1="56" y1="72" x2="40" y2="72" /> <line x1="40" y1="72" x2="40" y2="56" /> <line x1="40" y1="56" x2="24" y2="56" /> <line x1="24" y1="56" x2="24" y2="40" /> <line x1="24" y1="40" x2="24" y2="24" /> <line x1="24" y1="24" x2="40" y2="24" /> <line x1="40" y1="24" x2="40" y2="24" /> </g>
