행과 열의 미로 재귀 오류

Question

미로 구축에 필요한 모든 것이 포함 된 코드가 제공되었습니다. 제 직업은 미로 해결에 사용 된 makeMove 방법을 쓰는 것입니다.

protected void makeMove(int row, int col) 
{ 
    int MAX_ROWS = maze.length; 
    int MAX_COLS = maze.length; 
    boolean found = false; 
    boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS]; 
    //visited[startRow][startCol] = true; 
    if (row < 0 || row >= MAX_ROWS || col < 0 || col >= MAX_COLS || visited[row][col] || maze[row][col] == 1) 
     return; 

    visited[row][col] = true; 
    found = row == endRow && col == endCol; 

    /*if(row == endRow && col == endCol) { 
     found = true; 
    }*/ 
    if(!found && maze[row][col - 1]!=1 && !visited[row][col]) { // move left 
     makeMove(row, col -1); 
     visited[row][col -1] = true; 
    } 
    if(!found && maze[row - 1][col]!=1 && !visited[row-1][col]) { // move up 
     makeMove(row-1, col); 
     visited[row-1][col] = true; 
    } 
    if(!found && maze[row][col + 1]!=1 && !visited[row][col + 1]) { // move right 
     makeMove(row, col + 1); 
     visited[row][col + 1] = true; 
    } 
    if(!found && maze[row + 1][col]!=1 && !visited[row + 1][col]) { // move down 
     makeMove(row + 1, col); 
     visited[row + 1][col] = true; 
    } 

8 행과 8 열이있는 미로에 다음과 같이 실행

, 나는 스택 오버플로 오류가 계속 : 이것은 내가 지금까지 가지고있는 것입니다.

저는 오류가
42. MakeMove(row-1, col); //to move up
및 50.makeMove(row + 1, col); //to move down 될 라인 (42) 및 라인 (50)에 있음을 나타내는 것으로 판단.

이 두 가지에 논리적 오류가 있습니까?

Answer 1

미로의 현재 상태를 makeMove 메소드의 인수로 전달해야합니다. 귀하의 경우에는 미로의 상태가 방문 행렬입니다.

Answer 2

오류로 판단하면 코드가 호출 스택의 공간이 부족해지기 전에 올바르게 종료하지 않고 반복적으로 호출하는 알고리즘의 "무한 재귀"가 발생합니다. 이것은 스택 트레이스에 의해 지시 된 라인이 에러의 실제 원인이라는 것을 의미하는 것은 아니며, 프로그램의 공간이 부족한 곳이지만, 실제로는 결함이있는 로직은 보통 다른 곳에서 발생한다는 것을 명심하십시오. 확실히 문제를 일으키는

한 가지는 이것이다 : 이것은 논리 값의 새로운 2 차원 배열을 생성

boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS]; 

(또는 정확히 말하면, 불리언 배열의 배열) 재귀의 각 단계는과에 초기화 false (Java에서 부울 값의 기본값). 결과적으로 알고리즘은 각 재귀 단계가 각 타일이 아직 방문되지 않았 음을 나타내는 false으로 가득한 자체 배열을 갖기 때문에 이미 방문한 타일을 계속 방문합니다. 이 특정 문제는 각 재귀 호출에서 인수를 인수로 전달하거나 함수 외부에 저장하여 해결할 수 있습니다.

Answer 3

boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS]; 

각 재귀 호출에 대해 위의 상태를 생성하는 것은 상태 값을 저장하지 않습니다. 전역 변수로 유지하거나 인수로 전달하는 것이 더 좋습니다.