재귀 미로 해법

Question

0과 1로 채워진 2 차원 문자 배열이 주어진다면 0은 벽을 나타내고 1은 유효한 경로를 나타냅니다. findPath (int r, int c)라는 재귀 메서드를 개발하여 이탈을 찾습니다. 'x'표시가있는 미로에서 이 메서드는 미로의 현재 행과 열을 가져 와서 유효한 경로를 찾아 유효한 경로를 '+'로 표시 할 때까지 N, E, S, W 방향으로 이동합니다. 모든 방향이 벽에 의해 차단되는 것으로 밝혀지면,이 방법은 더 이상 그렇지 않을 때까지 역 추적을하고 그 경로를 'F'로 표시하여 잘못된 경로를 상징합니다.

지금 당장 필자는 findPath 메소드가 모든 방향을 가로 지르지 않는 이유를 알아낼 수 없다. 왜냐하면 내 디스플레이 방법이 내가 전달한 좌표에서 시작하여 거기에서부터 이동하지 않는 프로그램을 보여주기 때문이다. 이게 뭐야? 여기

내 드라이버 클래스

public class MazeMain2 
{ 
    public static void main(String[]args) 
    { 

    char[][] mazeArr = {{'0','0','0','1','0','0','0','0','0','0','0','0','0','0','0'}, 
       {'0','0','0','1','0','0','0','0','1','0','0','0','0','1','0'}, 
       {'0','0','0','1','1','1','1','1','1','1','1','1','0','0','0'}, 
       {'0','0','0','1','0','0','0','0','0','0','0','1','0','0','0'}, 
       {'0','0','0','1','1','1','1','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','0','0','0','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','1','1','1','1','0','0','0','1','0','0','0'}, 
       {'0','0','0','0','1','0','0','1','0','0','0','1','0','1','0'}, 
       {'0','0','0','0','1','0','0','1','0','0','0','0','0','0','0'}, 
       {'0','0','0','0','1','0','0','0','0','0','0','0','0','0','0'}, 
       {'0','0','0','0','1','1','1','1','1','1','1','0','0','0','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}, 
       {'0','0','0','0','0','1','0','0','0','0','1','1','1','1','0'}, 
       {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}}; 

    MazeSolver2 mazeS = new MazeSolver2(mazeArr); 

    mazeS.markEntry(); 
    mazeS.markExit(); 

    mazeS.solve(0, mazeS.start); 


    } 
} 

입니다 그리고 여기 findPath 방법 내 미로 해결사 클래스입니다

public class MazeSolver2 
{ 
    int start; 
    int exit; 

    char[][] maze; 

public MazeSolver2(char[][] currentMaze) 
{ 
    maze = currentMaze; 
} 

//Finds where the first 1 is in the top row of the 
//maze (entrance) 
public void markEntry() 
{ 
    for(int x = 0; x < maze.length; x++) 
    { 
     if(maze[0][x] == '1') 
     { 
      maze[0][x] = 'E'; 
      start = x; 
     } 
    } 
} 

//Finds where the last 1 is in the bottom row of the 
//maze (exit) 
public void markExit() 
{ 
    for(int x = 0; x < maze.length; x++) 
    { 
     if(maze[maze.length - 1][x] == '1') 
     { 
      maze[maze.length - 1][x] = 'x'; 
      exit = x; 
     } 
    } 
} 

public void solve(int x, int y) 
{ 
    if(findPath(x, y)) 
    { 
     System.out.println(maze[x][y]); 
    } 
    else 
     System.out.println("No solution"); 

} 

public boolean findPath(int r, int c) 
{ 
    displayMaze(maze); 

    //Found the exit 
    if(maze[r][c] == 'x') 
    { 
     return true; 
    } 


    if(maze[r][c] == '0' || maze[r][c] == '+' || maze[r][c] == 'F') 
    { 
     return false; 
    } 

    maze[r][c] = '+'; 

    //If row is currently at zero then don't check north 
    //direction because it will be outside of the maze 
    if(r <= 0) 
    { 
     if(findPath(r, c++)) 
     { 
      return true; 
     } 


     if(findPath(r++, c)) 
     { 
      return true; 
     } 

     if(findPath(r, c--)) 
     { 
      return true; 
     } 

    } 

    else 
    { 
     //check N, E, S, W directions 
     if(findPath(r--, c) || findPath(r, c++) || 
      findPath(r++, c) || findPath(r, c--)) 
     { 
      return true; 
     } 
    } 

    //Marking the bad path 
    maze[r][c] = 'F'; 

    return false; 

} 

//Displays maze 
public void displayMaze(char[][] maze) 
{ 

     for(int row = 0; row < maze.length; row++) 
     { 
      for(int col = 0; col < maze.length; col++) 
      { 
       if(col == 14) 
       { 
        System.out.print(maze[row][col]); 
        System.out.println(); 
       } 
       else 
       { 
        System.out.print(maze[row][col]); 
       } 
      } 
     } 

    System.out.println(); 
    } 
} 

Answer 1

귀하의 알고리즘은 내가하는 느낌이 좋지 않습니다 자체의 여러 흐름을 가지고 지적. 미로 탐색 문제를 검색하고 많은 유용한 자습서를 얻을 수 있습니다.

그러나 메소드 호출에주의하십시오. findPath(int r, int c)이 findPath(5, 5)으로 호출되면 findPath(r, c++)을 호출하면 findPath(5, 5)이 다시 전달되고 findPath(5, 6)은 전달되지 않습니다.

이 경우 findPath(r, c++)이 현재 값 c으로 호출되고 이후에 c++이 실행됩니다. 같은

는 사실이 방법 findPath()의 시작에서 값 int r, int c을 인쇄하는 것입니다 이해하는 등

, findPath(r, c--) findPath(r++ , c) 등을 위해 좋은 아이디어를 간다. 게시물 증가/감소 (x ++/- x)와 사전 증가/감소 (++ x/- x)로 약간 재생합니다.

희망이 있습니다.