Java迷宫 - 访问单元格问题

Question

我正在解决这个迷宫问题，我似乎无法得到保存已经访问过的单元格的点数的ArrayList正确。求解器只是保持闪烁。

这里是我的主类

import java.awt.Point; 
import java.util.*; 

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

    Maze aMaze = new Maze(8, 10); //creates a 8x10 Maze 
    MazeDisplay display = new MazeDisplay(aMaze); //creates a MazeDisplay with aMaze in it. 
    aMaze.buildMaze(20); //builds maze 

    //---- create a Stack to hold sequence of moves 
    Stack<Maze.Direction> myMoves = new Stack<Maze.Direction>(); 

    //---- create a Stack of type Point to note whether a cell has been visited 
    ArrayList<Point> visitedCells = new ArrayList<Point>(); 

    //---- use a while loop to check if the cell is open, follows algorithm to efficiently move through maze. If no other moves 
    //---- are available, it will pop the stack and go backward until it can move into a cell that has not been previously 
    //---- visited. 
    while (aMaze.goalReached() == false) 
    { 
     //---- create a new Point 
     Point myCell = new Point(aMaze.getCurrentRow(), aMaze.getCurrentCol()); 
     visitedCells.add(myCell); 

     //---- Step 1: check if the cell above is open. If so, move there, log that move in the stack, and mark visited. 
     if (aMaze.open(Maze.Direction.UP) == true && (!visitedCells.contains(myCell.getX()) && !visitedCells.contains(myCell.getY()-1))) 
     { 
      myCell.setLocation(aMaze.getCurrentRow(), aMaze.getCurrentCol()); 
      aMaze.move(Maze.Direction.UP); 
      myMoves.push(Maze.Direction.UP); 
      visitedCells.add(myCell); 

     } 
     //---- Step 2: check if the cell below is open. If so, move there, log that move in the stack, and mark visited. 
     else if (aMaze.open(Maze.Direction.DOWN) == true && (!visitedCells.contains(myCell.getX()) && !visitedCells.contains(myCell.getY()+1))) 
     { 
      myCell.setLocation(aMaze.getCurrentRow(), aMaze.getCurrentCol()); 
      aMaze.move(Maze.Direction.DOWN); 
      myMoves.push(Maze.Direction.DOWN); 
      visitedCells.add(myCell); 
     } 
     //---- Step 3: check if the cell to left is open. If so, move there, log that move in the stack, and mark visited. 
     else if (aMaze.open(Maze.Direction.LEFT) == true && (!visitedCells.contains(myCell.getX()-1) && !visitedCells.contains(myCell.getY()))) 
     { 
      myCell.setLocation(aMaze.getCurrentRow(), aMaze.getCurrentCol()); 
      aMaze.move(Maze.Direction.LEFT); 
      myMoves.push(Maze.Direction.LEFT); 
      visitedCells.add(myCell); 
     } 
     //---- Step 4: check if the cell to right is open. If so, move there, log that move in the stack, and mark visited. 
     else if (aMaze.open(Maze.Direction.RIGHT) == true && (!visitedCells.contains(myCell.getX()+1) && !visitedCells.contains(myCell.getY()))) 
     { 
      myCell.setLocation(aMaze.getCurrentRow(), aMaze.getCurrentCol()); 
      aMaze.move(Maze.Direction.RIGHT); 
      myMoves.push(Maze.Direction.RIGHT); 
      visitedCells.add(myCell); 
     } 
     else 
     { 
      Maze.Direction var = myMoves.pop(); 
      if (var == Maze.Direction.RIGHT) 
       aMaze.move(Maze.Direction.LEFT); 
      else if (var == Maze.Direction.LEFT) 
       aMaze.move(Maze.Direction.RIGHT); 
      else if (var == Maze.Direction.DOWN) 
       aMaze.move(Maze.Direction.UP); 
      else if (var == Maze.Direction.UP) 
       aMaze.move(Maze.Direction.DOWN); 

     } 
    } 
    //---- jumps out of loop when solved, prints statement below. 
    System.out.print("Maze is solved."); 
} 
} 

任何帮助，将不胜感激。

这里是迷宫类

import java.awt.*; 
import java.io.*; 
import java.util.*; 

public class Maze implements Serializable 
{ 
//-------data 
private int[ ][ ] mazeArray; 
private int currentArrayRow; 
private int currentArrayCol; 
private int goalArrayRow; 
private int goalArrayCol; 
private int buildAnimationDelay; 
private int solveAnimationDelay; 
private boolean alreadyBuilt; 

//-------constructors 
public Maze(int numRealRows, int numRealCols) 
{ 
    //since the maze is being created, initialize alreadyBuilt to false 
    alreadyBuilt = false; 

    //set the buildAnimationDelay and solveAnimationDelat to 0; they can be reset with methods 
    buildAnimationDelay = 0; 
    solveAnimationDelay = 0; 

    //make sure that the numRealRows and numRealCols are both > 1 (start cannot == goal) 
    if (numRealRows < 2) 
     throw new IllegalArgumentException("number of rows must be > 1"); 
    if (numRealCols < 2) 
     throw new IllegalArgumentException("number of columns must be > 1"); 

    //create the 2D array to hold the maze (its even rows/cols hold the walls, odd rows/cols hold the paint 
    mazeArray = new int[2*numRealRows+1][2*numRealCols+1]; 

    //since the even values are the walls, set anything with an even component to 1 (wall exists to start) 
    for (int row=0; row<mazeArray.length; row++) 
     for (int col=0; col<mazeArray[row].length; col++) 
      if (row%2==0 || col%2==0) //if either dimension is even... 
       mazeArray[row][col] = 1;  //its a wall, so set value to 1 

    //initialize the currentArrayRow and currentArrayCol to the upper left corner 
    currentArrayRow = 1; 
    currentArrayCol= 1; 
} 

// **************** methods ******************************************* 

//------- setSolveAnimationDelay - sets the delay (milliseconds) for the maze being solved (in case its animated) 
public void setSolveAnimationDelay(int theDelay) 
{ 
    solveAnimationDelay = theDelay; 
} 

//------- buildMaze - builds the Maze; calls other buildMaze method to set buildAnimationDelay to 0 
public void buildMaze() 
{ 
    buildMaze(0); 
} 

//------- buildMaze - builds the Maze; receives a delay to slow it down (in case its displayed) 
public void buildMaze(int buildAnimationDelay) 
{ 
    //if this maze has already been built and it trying to be built again, throw an exception 
    if (alreadyBuilt) 
     throw new IllegalStateException("cannot build maze - it has already been built"); 
    else 
     alreadyBuilt = true; //because we are NOW building it 

    //create a Stack to hold the cells we are visiting as it is built (they will be stored as Points) 
    //and an ArrayList to hold the "neighbors" in the code below 
    Stack<Point> cellStack = new Stack<Point>(); 
    ArrayList<Point> neighborAL; 

    //in the mazeArray, the even rows/cols are the walls, the odd rows/cols are the cells 
    int numRealRows = mazeArray.length/2; 
    int numRealCols = mazeArray[0].length/2; 

    //calculate the total number of (real) cells to visit 
    int totalCells = numRealRows * numRealCols; //rows x cols 

    //the odd rows/cols store the actual cells. Choose a random cell to start. 
    Random gen = new Random(); 
    int currentArrayRow = gen.nextInt(numRealRows)*2 + 1; //ex: if 3 real rows, this is a random from 1,3,5 
    currentArrayCol = gen.nextInt(numRealCols)*2 + 1;  //same for cols... 
    int lastArrayRow = currentArrayRow; 
    int lastArrayCol = currentArrayCol; 

    mazeArray[currentArrayRow][currentArrayCol] = 2; 
    int numVisitedCells = 1; 

    //while all cells have not been visited... 
    while(numVisitedCells < totalCells) 
    { 
     //go to sleep to slow down animation (based on its speed) 
     try{ Thread.sleep(buildAnimationDelay); } 
     catch(Exception ex) {} 

     //find all neighbors of currentCell with all walls intact 
     neighborAL = new ArrayList<Point>(); 
     //try cell above it 
     if (inMaze(currentArrayRow-2, currentArrayCol) && allWallsIntact(currentArrayRow-2, currentArrayCol)) 
      neighborAL.add(new Point(currentArrayRow-2, currentArrayCol)); 
     //try cell below it 
     if (inMaze(currentArrayRow+2, currentArrayCol) && allWallsIntact(currentArrayRow+2, currentArrayCol)) 
      neighborAL.add(new Point(currentArrayRow+2, currentArrayCol)); 
     //try cell to the left of it 
     if (inMaze(currentArrayRow, currentArrayCol-2) && allWallsIntact(currentArrayRow, currentArrayCol-2)) 
      neighborAL.add(new Point(currentArrayRow, currentArrayCol-2)); 
     //try cell to the right of it 
     if (inMaze(currentArrayRow, currentArrayCol+2) && allWallsIntact(currentArrayRow, currentArrayCol+2)) 
      neighborAL.add(new Point(currentArrayRow, currentArrayCol+2)); 

     //if neighbors with intact walls exist... 
     if (neighborAL.size() > 0) 
     { 
      //choose a neighbor at random 
      int randomInt = gen.nextInt(neighborAL.size()); 
      Point theNeighbor = neighborAL.get(randomInt); 
      int neighborRow = (int)theNeighbor.getX(); 
      int neighborCol = (int)theNeighbor.getY(); 

      //knock down the wall in between 
      if (currentArrayRow != neighborRow) //neighbor chosen was above or below 
       mazeArray[(currentArrayRow+neighborRow)/2][currentArrayCol] = 0; //knock down wall in between 
      else if (currentArrayCol != neighborCol) //neighbor chosen was to the left or right 
       mazeArray[currentArrayRow][(currentArrayCol+neighborCol)/2] = 0; //knock down wall in between 

      //push the current cell onto the cellStack 
      cellStack.push(new Point(currentArrayRow, currentArrayCol)); 

      //clear the current cell 
      mazeArray[currentArrayRow][currentArrayCol] = 0; 

      //make the new cell the current cell 
      currentArrayRow = neighborRow; 
      currentArrayCol = neighborCol; 
      mazeArray[currentArrayRow][currentArrayCol] = 2; 

      //add 1 to visitedCells 
      numVisitedCells++; 
     } 
     else 
     { 
      //clear the current cell 
      mazeArray[currentArrayRow][currentArrayCol] = 0; 

      //pop the most recent entry off of cellStack and make it the current cell 
      Point popped = cellStack.pop(); 
      currentArrayRow = (int)popped.getX(); 
      currentArrayCol = (int)popped.getY(); 
      mazeArray[currentArrayRow][currentArrayCol] = 2; 
     } 
    } //end while 

    //clear the cell that ended up as the current Cell 
    mazeArray[currentArrayRow][currentArrayCol] = 0; 

    //set the current cell to the upper left corner 
    currentArrayRow = 1; 
    currentArrayCol = 1; 
    mazeArray[currentArrayRow][currentArrayCol] = 2; //current 

    //set the goal to the lower right corner 
    goalArrayRow = numRealRows*2-1; 
    goalArrayCol = numRealCols*2-1; 
    mazeArray[goalArrayRow][goalArrayCol] = 3; //goal 
} 

//-------- allWallsIntact - returns true if the cell at [aRow][aCol] has all walls around it intact 
private boolean allWallsIntact(int aRow, int aCol) 
{ 
    return (mazeArray[aRow-1][aCol] == 1 && //wall above it exists 
        mazeArray[aRow+1][aCol] == 1 && //wall below it exists 
        mazeArray[aRow][aCol-1] == 1 && //wall to the left exists 
        mazeArray[aRow][aCol+1] == 1);   //wall to the right exists 
} 

//-------- inMaze - returns true if the cell at [aRow][aCol] is in the maze 
private boolean inMaze(int aRow, int aCol) 
{ 
    return (aRow > 0 && aRow < mazeArray.length-1 && 
        aCol > 0  && aCol < mazeArray[0].length-1); 
} 

//-------- getCurrentRow - returns the current (real) row 
public int getCurrentRow() 
{ 
    return currentArrayRow/2; 
} 

//-------- getCurrentCol - returns the current (real) col 
public int getCurrentCol() 
{ 
    return currentArrayCol/2; 
} 


//-------- open - returns true if there is no wall in the direction that is passed in 
public boolean open(Direction direction) 
{ 
    boolean result = false; 
    if (direction == Direction.UP && mazeArray[currentArrayRow-1][currentArrayCol]==0) 
     result = true; 
    else if (direction == Direction.DOWN && mazeArray[currentArrayRow+1][currentArrayCol]==0) 
     result = true; 
    else if (direction == Direction.LEFT && mazeArray[currentArrayRow][currentArrayCol-1]==0) 
     result = true; 
    else if (direction == Direction.RIGHT && mazeArray[currentArrayRow][currentArrayCol+1]==0) 
     result = true; 

    return result; 
} 

//-------- openTo - returns true if the current cell is openTo (no wall) the one passed in 
private boolean openTo(int aRow, int aCol) 
{ 
    boolean result; 

    if (!adjacentTo(aRow, aCol)) 
     result = false; 
    else if (currentArrayRow-aRow == 2) //IS adjacent, figure which direction and call other method 
     result = mazeArray[currentArrayRow-1][currentArrayCol]==0; //UP 
    else if (currentArrayRow-aRow == -2) 
     result = mazeArray[currentArrayRow+1][currentArrayCol]==0; //DOWN 
    else if (currentArrayCol-aCol == 2) 
     result = mazeArray[currentArrayRow][currentArrayCol-1]==0; //LEFT 
    else if (currentArrayCol-aCol == -2) 
     result = mazeArray[currentArrayRow][currentArrayCol+1]==0; //RIGHT 
    else 
     result = false; 

    return result; 
} 

//-------- adjacentTo - returns true if the current cell is adjacentTo (above/below/left/right) current cell 
public boolean adjacentTo(int aRow, int aCol) 
{ 
    //calculate how far the move is (hopefully row OR col is just +-2) 
    int arrayRowChange = currentArrayRow - aRow; 
    int arrayColChange = currentArrayCol - aCol; 

    //it is adjacent if EITHER the rows or the cols differ by 2 
    return Math.abs(arrayRowChange)==2^Math.abs(arrayColChange)==2; //checking row xor col 
} 

// -------- move - receives a Direction and moves there if OK. Calls the other 
//     arrayMove to do this 
public boolean move(Direction direction) 
{ 
    boolean success = false; 

    if (direction == Direction.UP) 
     success = arrayMove(currentArrayRow-2, currentArrayCol); 
    else if (direction == Direction.DOWN) 
     success = arrayMove(currentArrayRow+2, currentArrayCol); 
    else if (direction == Direction.LEFT) 
     success = arrayMove(currentArrayRow, currentArrayCol-2); 
    else if (direction == Direction.RIGHT) 
     success = arrayMove(currentArrayRow, currentArrayCol+2); 

    return success; 
} 

//-------- move - receives the literal (not array) row/col to move to. Calls the 
//    other ArrayMove to do this. 
private boolean move(int realRow, int realCol) 
{ 
    return arrayMove(2*realRow+1, 2*realCol+1); 
} 

//-------- arrayMove - moves using the maze array (moves a distance of 2 to get to next cell) 
//      first checks to see if move is legal. 
private boolean arrayMove(int newArrayRow, int newArrayCol) 
{ 
    boolean success; 

    //go to sleep to slow down animation (based on its speed) 
    try{ Thread.sleep(solveAnimationDelay); } 
    catch(Exception ex) {} 

    //make sure the new row/col is still in the maze 
    if (!inMaze(newArrayRow, newArrayCol)) 
     throw new IllegalMazeMoveException("trying to move to cell <" + newArrayRow/2 + ", " + 
       newArrayCol/2 + "> which is outside the maze"); 

    //make sure the new row/col is adjacent 
    else if (!adjacentTo(newArrayRow, newArrayCol)) 
     throw new IllegalMazeMoveException("trying to move from cell <" + currentArrayRow/2 + ", " + currentArrayCol/2 + 
       "> to non-adjacent cell <" + newArrayRow/2 + ", " + newArrayCol/2 + ">"); 

    //make sure there is not a wall in between 
    else if (!openTo(newArrayRow, newArrayCol)) 
     throw new IllegalMazeMoveException("trying to move from cell <" + currentArrayRow/2 + ", " + currentArrayCol/2 + 
       "> to cell <" + newArrayRow/2 + ", " + newArrayCol/2 + "> and there is a wall in between"); 

    //if OK, move the current cell 
    else 
    { 
     //if new ArrayRow is already in the path, then we are retreating from current location so 
     //clear current location 
     if (mazeArray[newArrayRow][newArrayCol] == 2) 
      mazeArray[currentArrayRow][currentArrayCol] = 0; 

     currentArrayRow = newArrayRow; 
     currentArrayCol = newArrayCol;      //move current cell 
     mazeArray[currentArrayRow][currentArrayCol] = 2; //and show it as part of path 
     success = true; 

    } 

    //return 
    return success; 
} 

//-------- goalReached - returns true if the maze is solved (current location == goal) 
public boolean goalReached() 
{ 
    return (currentArrayRow == goalArrayRow && currentArrayCol == goalArrayCol); 
} 

//-------- getMazeArray - returns the mazeArray 
public int[][] getMazeArray() 
{ 
    return mazeArray; 
} 

//*********************************************************************** 

//This is Maze's enumerated data type: moves can be UP, DOWN, LEFT, RIGHT 
public enum Direction 
{ 
    UP, DOWN, LEFT, RIGHT 
} 

//*********************************************************************** 

//MazeMoveException will be thrown when an illegal move is requested in the maze 
public class IllegalMazeMoveException extends IllegalArgumentException 
{ 
    //no data is needed - all inherited... 

    //constructor - just do what the parent class would do if it received the String 
    public IllegalMazeMoveException(String str) 
    { 
     super(str); 
    } 

    //no methods are needed - all inherited... 
} 

}

Answer 1

下列不看的权利：

(!visitedCells.contains(myCell.getX()) && !visitedCells.contains(myCell.getY()-1))) 

这里，visitedCells是ArrayList<Point>，但上面的代码看起来两个独立Integer s。

相反，您需要构建一个Point的实例，并查找该实例，确保使用Point.equals()来比较坐标。

这个错误在几个地方重复。