Backtracking-Methode zur Lösung des Labyrinthproblems

Einführung

Ich habe kürzlich einige Algorithmusfragen zu Leetcode gelesen. Einige davon sahen sehr einfach und häufig verwendet aus, aber ich konnte nicht herausfinden, wie ich sie lösen kann, zum Beispiel: 实现sqrt函数,求数组的排列 . Wenn Sie nicht gut in fortgeschrittener Mathematik sind, werden diese scheinbar einfachen Probleme beim ersten Mal schwer zu lösen sein. Natürlich werden wir heute über ein solches Problem sprechen, wie man alle Lösungen dafür löst Labyrinth. So lösen Sie dieses Problem: Wenn Sie die Idee des Zurückverfolgens nicht verstehen, werden viele etwas komplexere Probleme schwer zu lösen sein.

Problembeschreibung

Ich bin beim Umherwandern auf dieses Problem gestoßen und kann mich nicht genau erinnern, wo es ist.

<code>1   1   1   1

0   1   0   1

0   1   0   1

0   1   1   1</code>

Die obere linke Ecke ist der Eingang und die untere rechte Ecke ist der Ausgang. Xiao Meng (ja, Sie haben es richtig gelesen, es ist Xiao Ming mit Gras) kommt herein Eingang und Flucht aus dem Ausgang (Wenn Sie nicht innerhalb einer Stunde entkommen können, werden Sie von X Monstern gefressen), wobei 1 bedeutet, dass es passierbar ist und 0 bedeutet, dass es unpassierbar ist. Sie können nur in zwei Richtungen gehen: rechts und Finden Sie alle möglichen Fluchtwege für die Kleinen.

Diese Frage scheint recht einfach zu sein, und Sie können die Antwort sofort sehen, aber ich weiß nicht, wo ich anfangen soll, wenn ich Gedanken in Code übertrage.

So lösen Sie

Eine Lösung für dieses Problem ist die Backtracking-Methode. Werfen wir einen Blick auf die Definition der Backtracking-Methode (Baidu-Enzyklopädie):

Die Backtracking-Methode (Erkundungs- und Backtracking-Methode) ist eine Optimierungssuchmethode, auch als heuristische Methode bekannt, die gemäß den Optimierungsbedingungen nach vorne sucht, um das Ziel zu erreichen. Aber wenn Sie einen bestimmten Schritt in der Erkundung erreichen und feststellen, dass die ursprüngliche Wahl nicht optimal ist oder das Ziel nicht erreichen kann, werden Sie einen Schritt zurücktreten und eine andere Wahl treffen. Diese Technik des Zurückgehens und erneuten Versuchens funktioniert nicht ist die Backtracking-Methode, und der Punkt in einem bestimmten Zustand, der die Backtracking-Bedingungen erfüllt, wird als „Lookback-Punkt“ bezeichnet.

Meine Idee:

• Die obere linke Ecke ist (0,0), die untere rechte Ecke ist (3,3) und andere Punkte im Koordinatensystem verstreut
  
• Beginnen Sie bei (0,0)
  
• Beginnen Sie am angegebenen Koordinatenpunkt, suchen Sie zuerst nach rechts, wenn es 1 ist, fahren Sie fort , es ist 0 Wenn Sie nach unten suchen, notieren Sie die Koordinaten, die vor der Suche gesucht wurden
  
• Wenn die Koordinaten gleich (3,3) sind, handelt es sich zu diesem Zeitpunkt um einen Backtracking-Punkt 🎜>
  Solange Sie die Grenze nicht überschreiten, wiederholen Sie den dritten Schritt
• Sehen Sie sich meine PHP-Implementierung an:

Das Obige stellt die Backtracking-Methode zur Lösung des Labyrinthproblems vor, einschließlich der relevanten Aspekte. Ich hoffe, dass es für Freunde hilfreich ist, die sich für PHP-Tutorials interessieren.

<code><?php
$nums = [
    [1,1,1,1,1,1],
    [0,1,0,1,0,1],
    [0,1,0,1,0,1],
    [0,1,1,1,1,1]
];
function getRet($data, $x, $y, &$result=[], $record)
{
    $snapshort = [];
    $xL = count($data) - 1;
    $yL = count($data[0]) - 1;

    if($x > $xL || $y > $yL) {
        //跑到迷宫不存在的空间了，这种事情绝对不能发生
        return;
    }

    if($data[$x][$y] == "0") {
        //是0的话停止继续前进，退回上一状态
        return;
    } elseif($data[$x][$y] == "1") {
        //是1的话，记录最新的坐标到当前已找到的路径中，继续向前搜索
        //如果到达出口，记录答案并回溯
        $snapshort = array_merge($record, [[$x, $y]]);
        if($x == $xL && $y == $yL) {
            $result[] = array_merge($record, [[$x, $y]]);
            return;
        }
    } else {
        return;
    }       

    //向有搜索
    //这里的$snapshort保存当前搜索位置的状态，等到下次回溯到这里的时候会用到
    getRet($data, $x, ++$y, $result, $snapshort);

    //向下搜索
    getRet($data, ++$x, --$y, $result, $snapshort);
}


//看个例子    
$result = [];
getRet($nums, 0, 0, $result, []);

foreach ($result as $pos) {
    foreach ($pos as $xy) {
        echo "({$xy[0]},{$xy[1]}) => ";
    }
    echo "end\n";
}

//输出结果
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(0,4)=>(0,5)=>(1,5)=>(2,5)=>(3,5)=>end
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(1,3)=>(2,3)=>(3,3)=>(3,4)=>(3,5)=>end
(0,0)=>(0,1)=>(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)=>(3,4)=>(3,5)=>end</code>