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) 위치에 위치하고 오른쪽으로 걸어갑니다. 그리고 경계를 만나면, 대신 내려가다가 다시 경계를 만나서 왼쪽으로 바꿨습니다....

조심스러운 사람은 곧 패턴을 발견할 것입니다:

미로 속의 사람은 네 가지 기본 여행 전략을 가지고 있습니다.

1. 오른쪽으로 걸어갈 때 경계선을 만나거나 오른쪽의 그리드를 지나갔다면 내려가고, 그렇지 않으면 계속 오른쪽으로 가세요.

2. 내려갈 때 경계선을 만나거나 아래 그리드를 지나갔다면 왼쪽으로 가고, 그렇지 않으면 계속해서 걸어갑니다.

3. 왼쪽으로 걸을 때 경계선을 만나거나 왼쪽의 그리드를 지나갔다면 위로 올라가고, 그렇지 않으면 계속 왼쪽으로 가세요.

4. 위쪽으로 걸어갈 때 경계선을 만나거나 위쪽 그리드를 넘으면 오른쪽으로 가고, 그렇지 않으면 계속 위쪽으로 걸어갑니다.

보시다시피 이것은 재귀적인 과정인데 언제 종료되나요?

이 사람이 모든 그리드를 방문하면 종료됩니다.

아래 제가 작성한 프로그램은 부울 유형의 2차원 배열을 사용하여 그리드 통과 여부를 기록합니다.

각각 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 질문: 나선형 행렬입니다. 더 많은 관련 내용을 보려면 PHP 중국어 웹사이트(www.php.cn)를 주목하세요!