JavaScript Fun Question: Spiral Matrix-JS Tutorial-php.cn

JavaScript Fun Question: Spiral Matrix

黄舟

Release： 2017-01-22 14:58:38

Original

1423 people have browsed it

Given an n * n two-dimensional array, use the spiral matrix algorithm to traverse it and return the path.

The example is as follows:

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

Copy after login

The example of this program may not be intuitive, so let’s take a picture to show the process.

JavaScript Fun Question: Spiral Matrix

As you can see, it is like a person moving forward in a maze. It is first located at the position (0,0), then walks to the right, and when it encounters the boundary, it Instead, I walked down and encountered the boundary again, so I changed to the left....

Careful people will soon discover a pattern:

The person in the maze has Four basic travel strategies.

1. When walking to the right, if you encounter the boundary or the grid on the right has been passed, then go down, otherwise continue to go right.

2. When walking down, if you encounter a boundary or the grid below has been passed, then go left, otherwise continue walking down.

3. When walking left, if you encounter the boundary or the grid on the left has been passed, then go up, otherwise continue to go left.

4. When walking upward, if you encounter a boundary or the upper grid has been passed, then go right, otherwise continue walking upward.

As you can see, this is a recursive process, so when will it terminate?

When this person has visited every grid, it will terminate.

The program I wrote below uses a two-dimensional array of boolean type to record whether the grid has been passed.

Introduces four functions, up, down, left and right, representing four strategies respectively.

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

Copy after login

The above is the content of interesting JavaScript questions: spiral matrix. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!