欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JavaScript趣题:螺旋矩阵

程序员文章站 2022-03-19 19:36:37
...
给定一个n * n的二维数组,使用螺旋矩阵算法,遍历它,并返回路径。

例子如下:

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

这个程序的例子可能不太直观,那就上个图来展示下它这个过程。

JavaScript趣题:螺旋矩阵

大家可以看到,就好比一个人在迷宫里面前进,它首先位于(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)!