给定一个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)!