JavaScript の楽しい質問: スパイラル マトリックス

n*n の 2 次元配列が与えられた場合、スパイラル行列アルゴリズムを使用してそれを走査し、パスを返します。

例は次のとおりです:

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

このプログラムの例は直感的ではないかもしれないので、プロセスを示すために写真を撮りましょう。

ご覧のとおり、人が迷路の中を前進しているようなものです。最初は (0,0) の位置に位置し、次に右に歩き、境界に遭遇し、次に下に歩き始めます。

慎重な人はすぐにパターンを発見します:

迷路の中にいる人には 4 つの基本的な移動戦略があります。

1. 右に歩いているときに、境界線に遭遇するか、右側のグリッドを通過した場合は下に進み、そうでない場合は右に進みます。

2. 下に歩いているときに、境界線に遭遇するか、下のグリッドを通過した場合は左に進み、そうでない場合は下に進みます。

3. 左に歩くとき、境界線に遭遇するか、左側のグリッドを通過した場合は上に進み、そうでない場合は左に進みます。

4. 上に向かって歩くとき、境界に遭遇するか、上のグリッドを通過した場合は右に進み、そうでない場合は上に歩き続けます。

ご覧のとおり、これは再帰的なプロセスなので、いつ終了するのでしょうか?

この人がすべてのグリッドを訪問すると、終了します。

以下に書いたプログラムは、ブール型の二次元配列を使用して、グリッドを通過したかどうかを記録します。

4 つの機能を紹介します: 上、下、左、右、それぞれ 4 つの戦略を表します。

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;  
}

上記は、JavaScript に関する興味深い質問の内容です: Spiral Matrix の関連コンテンツについては、PHP 中国語 Web サイト (www.php.cn) に注目してください。