Lustige JavaScript-Frage: Spiralmatrix

Verwenden Sie bei einem gegebenen zweidimensionalen n * n-Array den Spiralmatrix-Algorithmus, um es zu durchlaufen und den Pfad zurückzugeben.

Das Beispiel sieht wie folgt aus:

array = [[1,2,3],  
      [4,5,6],  
      [7,8,9]]  
snail(array) // => [1,2,3,6,9,8,7,4,5]

Das Beispiel dieses Programms ist möglicherweise nicht intuitiv, also machen wir ein Foto, um den Vorgang zu zeigen.

Wie Sie sehen können, ist es wie eine Person, die sich in einem Labyrinth vorwärts bewegt. Sie befindet sich zunächst an der Position (0,0) und geht dann nach rechts. und wenn es auf die Grenze trifft, bin ich stattdessen nach unten gegangen und bin wieder auf die Grenze gestoßen, also bin ich nach links gewechselt....

Eine vorsichtige Person kann schnell ein Muster entdecken:

Die Person im Labyrinth verfügt über vier grundlegende Reisestrategien.

1. Wenn Sie beim Gehen nach rechts auf die Grenze stoßen oder das Gitter auf der rechten Seite überschritten wurde, gehen Sie nach unten, andernfalls gehen Sie weiter nach rechts.

2. Wenn Sie beim Abstieg auf eine Grenze stoßen oder das Gitter darunter überschritten wurde, gehen Sie nach links, andernfalls gehen Sie weiter abwärts.

3. Wenn Sie beim Gehen nach links auf die Grenze stoßen oder das Gitter auf der linken Seite überschritten wurde, gehen Sie nach oben, andernfalls gehen Sie weiter nach links.

4. Wenn Sie beim Aufwärtsgehen auf eine Grenze stoßen oder das obere Gitter überschritten wurde, gehen Sie nach rechts, andernfalls gehen Sie weiter nach oben.

Wie Sie sehen, handelt es sich um einen rekursiven Prozess. Wann wird er also beendet?

Wenn diese Person jedes Gitter besucht hat, endet es.

Das Programm, das ich unten geschrieben habe, verwendet ein zweidimensionales Array vom Typ Boolean, um aufzuzeichnen, ob das Gitter passiert wurde.

Führt vier Funktionen ein: oben, unten, links und rechts, die jeweils vier Strategien darstellen.

function snail(array) {  
    //当前行  
    var row = 0;  
    //当前列  
    var col = 0;  
    //对应的存放boolean值的二维数组  
    var hasVisited = [];  
    //存放结果的数组  
    var result = [];  
    //数组元素个数  
    var size = array.length * array[0].length;  
      
    //boolean二维数组初始化  
    for (var i = 0; i < array.length; i++) {  
        var temp = [];  
        var len = array[i].length;  
        for (var j = 0; j < len; j++) {  
            temp.push(false);  
        }  
        hasVisited.push(temp);  
    }  
  
    function right() {  
        if (result.length < size) {  
            result.push(array[row][col]);  
            hasVisited[row][col] = true;  
            if (col + 1 >= array.length || hasVisited[row][col + 1]) {  
                row += 1;  
                down();  
            } else {  
                col += 1;  
                right();  
            }  
        }  
    }  
  
    function down() {  
        if (result.length < size) {  
            result.push(array[row][col]);  
            hasVisited[row][col] = true;  
            if (row + 1 >= array.length || hasVisited[row + 1][col]) {  
                col -= 1;  
                left();  
            } else {  
                row += 1;  
                down();  
            }  
        }  
    }  
  
    function left() {  
        if (result.length < size) {  
            result.push(array[row][col]);  
            hasVisited[row][col] = true;  
            if (col == 0 || hasVisited[row][col - 1]) {  
                row -= 1;  
                up();  
            } else {  
                col -= 1;  
                left();  
            }  
        }  
    }  
  
    function up() {  
        if (result.length < size) {  
            result.push(array[row][col]);  
            hasVisited[row][col] = true;  
            if (hasVisited[row - 1][col]) {  
                col += 1;  
                right();  
            } else {  
                row -= 1;  
                up();  
            }  
        }  
    }  
    //首先往右走  
    right();  
    return result;  
}

Das Obige ist der Inhalt interessanter JavaScript-Fragen: Spiralmatrix Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!