JavaScript趣題：螺旋矩陣

給定一個n * n的二維數組，使用螺旋矩陣演算法，遍歷它，並返迴路徑。

例子如下：

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

這個程式的例子可能不太直觀，那就上個圖來展示下它這個過程。

大家可以看到，就好比一個人在迷宮裡面前進，它首先位於(0,0)這個位置，接著向右走，遇到邊界，就改為向下走，又遇到了邊界，改為向左走....

細心的人，很快就可以發現一個規律：

迷宮裡的這個人有四種基本行進策略。

1.當向右走，如果遇到邊界，或者右邊的格子已經走過，那麼就向下走，否則繼續向右走。

2.當向下走，如果遇到邊界，或者下邊的格子已經走過，那麼就向左走，否則繼續向下走。

3.當向左走，如果遇到邊界，或者左邊的格子已經走過，那麼就向上走，否則繼續向左走。

4.當向上走，如果遇到邊界，或者上邊的格子已經走過，那麼就向右走，否則繼續向上走。

大家可以看出來，這是一個遞歸的過程，那麼，何時終止呢？

當每一個格子，這個人都訪問過了時，那麼就終止了。

我下面寫的程序，用到了一個boolean類型的二維數組，記錄格子是否已經走過。

引入了上下左右四種函數，分別表示四種策略。

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趣題：螺旋矩陣的內容，更多相關內容請關注PHP中文網（www.php.cn）！