미로를 재귀 적으로 풀어 냄

Question

나는이 질문이 전에 물어 왔다는 것을 알고 있지만, 나는 그 해답을 볼 수 없다는 것을 알고있다.

import java.io.Serializable; 
import java.awt.Color; 

public class Maze implements Serializable { 

/** 
* 
*/ 
private static final long serialVersionUID = -787488019846627488L; 
/** 
* the north wall of a room 
*/ 
public static final int NORTH = 0; 
/** 
* the east wall of a room 
*/ 
public static final int EAST = 1; 
/** 
* the south wall of a room 
*/ 
public static final int SOUTH = 2; 
/** 
* the west wall of a room 
*/ 
public static final int WEST = 3; 
/** 
* No direction from a room 
*/ 
public static final int NO_DIRECTION = 4; 
private static String[] walls = {"North", "East", "South", "West"}; 
private Room[][] rooms; 

/** 
* Constructor 
* @param rows is the number of rows in the maze 
* @param columns is the number of columns in the maze 
*/ 
public Maze(int rows, int columns) { 
    rooms = new Room[rows][columns]; 
    for (int i = 0; i < rows; i++) { 
     for (int j = 0; j < columns; j++) { 
      rooms[i][j] = new Room(); 
     } // end for 
    } // end for 
} 

/** 
* rows accessor 
* @return the number of rows in the maze 
*/ 
public int getRows() { 
    return rooms.length; 
} 

/** 
* columns accessor 
* @return the number of columns in the maze 
*/ 
public int getColumns() { 
    return rooms[0].length; 
} 

/** 
* Checks to see if a wall is closed 
* @param row the row number 
* @param column the column number 
* @param wall the wall number 
* @return true if wall is closed; false if it is open 
*/ 
public boolean isClosed(int row, int column, int wall) { 
    return rooms[row][column].closed[wall]; 
} 

/** 
* Opens the wall 
* @param row the row number 
* @param column the column number 
* @param wall the wall number 
*/ 
public void setOpen(int row, int column, int wall) { 
    rooms[row][column].closed[wall] = false; 
} 

/** 
* Closes the wall 
* @param row the row number 
* @param column the column number 
* @param wall the wall number 
*/ 
public void setClosed(int row, int column, int wall) { 
    rooms[row][column].closed[wall] = true; 
} 

public static class Door { 

    int row; 
    int column; 
    int wall; 
    Color color; 

    public Door(int row, int column, int wall, Color color) { 
     this.row = row; 
     this.column = column; 
     this.wall = wall; 
     this.color = color; 
    } // end constructor 

    public boolean equals(Object x) { 
     if (x == null) return false; 
     if (!(x.getClass().equals(this.getClass()))) { 
      return false; 
     } 
     Door door = (Door) x; 
     return row == door.row && column == door.column && wall == door.wall && color.equals(door.color); 
    } // end equal 

    public int hashCode() { 
     return row + column + wall + color.hashCode(); 
    } 

    public String toString() { 
     return row + " " + column + " " + walls[wall] + "\n"; 
    } // end toString() 
} // end Door 

private class Room implements Serializable { 

    boolean[] closed; 

    Room() { 
     closed = new boolean[4]; 
     for (int i = 0; i < 4; i++) { 
      closed[i] = true; 
     } // end for 
    } 
} // end Room 
} // end Maze 

나는 내가에있어 생각 : 여기

import java.awt.Color; 
import java.util.ArrayList; 

public class RecursiveMazeSolution implements MazeSolver { 
boolean[][] marked; 
ArrayList<Maze.Door> solutionPath = new ArrayList<>(); 

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) { 
    marked = new boolean[maze.getRows()][maze.getColumns()]; 
    return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked); 
} 

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) { 
    System.out.println(startRow + " " + startCol + " " + finishRow + " " + finishCol); 
    if(startRow < 0 || startCol < 0 || startRow > maze.getRows() - 1|| startCol > maze.getColumns() - 1) return null; 
    if(marked[startRow][startCol]) { 
     System.out.println("I'm inside marked if"); 
     return null; 
    } 

    marked[startRow][startCol] = true; 
    if(startRow == finishRow && startCol == finishCol) { 
     solutionPath.add(new Maze.Door(startRow, startCol, Maze.NO_DIRECTION, Color.RED)); 
     return solutionPath; 
    } 

    if(solveMaze(startRow - 1, finishRow, startCol, finishCol,maze, marked) != null && !maze.isClosed(startRow, startCol, Maze.NORTH)) { 
     solutionPath.add(new Maze.Door(startRow, startCol, Maze.NORTH, Color.RED)); 
     return solutionPath; 
    } 
    if(solveMaze(startRow + 1, finishRow, startCol, finishCol,maze, marked) != null && !maze.isClosed(startRow, startCol, Maze.SOUTH)){ 
     solutionPath.add(new Maze.Door(startRow, startCol, Maze.SOUTH, Color.RED)); 
     return solutionPath; 
    } 
    if(solveMaze(startRow, finishRow, startCol - 1, finishCol,maze, marked) != null && !maze.isClosed(startRow, startCol, Maze.WEST)){ 
     solutionPath.add(new Maze.Door(startRow, startCol, Maze.WEST, Color.RED)); 
     return solutionPath; 
    } 
    if(solveMaze(startRow, finishRow, startCol + 1, finishCol,maze, marked) != null && !maze.isClosed(startRow, startCol, Maze.EAST)){ 
     solutionPath.add(new Maze.Door(startRow, startCol, Maze.EAST, Color.RED)); 
     return solutionPath; 
    } 

    return null; 
} 


} 

가 나에게 제공 한 미로 클래스입니다 : 내가 여기 재귀 미로 솔루션을 작성하고 가정하고하는 것은 지금까지 한 일이다 솔루션에 옳은 방법이지만, 내 프로그램은 단순히 재귀 적으로 얼마 동안 실행하고 미로에 대한 해결책을 찾지 못합니다. 또한 내 프로그램에서 "벽"을 무시하게 만들면 많은 재귀 호출 이후에 솔루션을 찾을 수 있지만 벽을 무시하지는 않습니다. 누구든지 내가 뭘 잘못하고 있는지 말해 줄래?

Answer 1

코드를 한 눈에 보면 방문한 정사각형을 solveMaze에 방문하면 안된다고 생각합니다. 함수를 입력 할 때 사각형을 표시하면 다시 볼 수 없다고 말합니다. 하지만 돌아 오기 전에 다시 자유로 표시해야합니다.

이것에 대해 조금 더 생각한 후에는 해당 사각형을 통해 솔루션 경로가 없다는 것을 확인한 후 사각형의 선택을 취소해야하므로 일반적으로 문제가되지 않는 것으로 보입니다.

그렇다면 재귀 호출 후 벽 테스트를 수행하고 있다는 것을 깨달았습니다. 즉, 벽을 통해 해결책을 찾고, 그 다음에는 벽이 있기 때문에 해결책을 포기하는 것입니다. 그 사이에 방문한 모든 사각형을 표시하고 유효한 해결책을 찾을 곳이 없습니다.

전에 재귀를 수행해야하며 벽이 있으면 재귀를 수행하지 않아도됩니다. 단락 평가 (당신의 if 문에서 조건을 재정렬하여) 여기에 충분하다 :

그런데

if(!maze.isClosed(startRow, startCol, Maze.NORTH) && 
    solveMaze(startRow-1, finishRow, startCol, finishCol,maze, marked) != null) 

, 매개 변수로 marked을 통과 할 필요가 없습니다. 그것은 반원입니다.