该程序旨在通过读取文本文件来创建并解决鼠标从迷宫中逃生的路线。有一个Maze类，它基本上是MazeElement的2D数组，MazeElement包含一个char变量和一个位置对象；位置保持2D阵列上的每个元素的坐标。到目前为止，该程序有效地读取并创建了2D阵列。问题在于backTracking算法。我使用堆栈来实现回溯，但回溯似乎只从输出循环一次。我不知道你是否能从下面的代码中注意到一些东西：导入java.io.；导入java.util.；
public class MazeSolver
{
public static void main (String [] parms)
{
Maze maze = new Maze();
maze.displayMaze();
maze.backTracking();
maze.displayMaze();
}
}
//**********************************
//*******Position class*************
//**********************************
class Position
{
private int row;
private int col;
public Position()
{
row =0;
col =0;
}
public Position (int x, int y)
{
row = x;
col = y;
}
public void setRow(int x)
{
row = x;
}
public void setCol(int y)
{
col = y;
}
public int getRow()
{
return row;
}
public int getCol()
{
return col;
}
//NOTE: wrote for testing purposes, to see the mouse and exit positions
public String getPosition()
{
return row + ", " + col;
}
}//end Position
//**********************************
//*******Maze element class*********
//**********************************
class MazeElement
{
private char letter;
private Position prevPosition;
public MazeElement(char c, Position p)
{
this.letter = c;
this.prevPosition = p;
}
public char getLetter()
{
return letter;
}
public Position getPosition()
{
return prevPosition;
}
public void setPosition(Position p)
{
this.prevPosition = p;
}
public void setLetter(char c)
{
this.letter = c;
}
public void printElement()
{
System.out.print(letter + " ");
}
}//end MazeElement
//**********************************
//*******Maze class*****************
//**********************************
class Maze
{
private MazeElement [][] maze;
private int numRows;
private int numCols;
private Position start;
private Position exit;
BufferedReader inFile;
Scanner kbd = new Scanner(System.in);
String inLine;
String fileName;
String [] tokens;
public Maze()
{
try
{
System.out.println("Input file name");
fileName = kbd.next();
inFile = new BufferedReader(new FileReader(fileName));
inLine = inFile.readLine();
tokens = inLine.trim().split("\s+");
numRows = Integer.parseInt(tokens[0]);
numCols = Integer.parseInt(tokens[1]);
maze = new MazeElement[numRows][numCols];
for(int row = 0; inLine != null && row < numRows; row++)
{
inLine = inFile.readLine();
tokens = inLine.trim().split("\s+");
for(int col = 0; col < numCols; col++)
{
maze[row][col] = new MazeElement(tokens[col].charAt(0),null);
}
}
inFile.close();
//finding m and e from the maze
for (int i = 0; i < maze.length; i++)
{
for (int j = 0; j < maze[i].length; j++)
{
char letter = maze[i][j].getLetter();
if(letter == 'm')
{
start = new Position(i,j);
}
if(letter == 'e')
{
exit = new Position(i,j);
}
}
}
}//end try block
catch (IOException ioe)
{
System.out.println(ioe.getMessage());
}
}//end public Maze()
public void backTracking()
{
Stack<Position> theStack = new Stack<Position>();//initialise stack
Position goal = exit;
Position curr;
MazeElement north, south, east, west;
int currRow, currCol;
curr = null;
boolean foundGoal = false;
theStack.push(start);
while((!foundGoal) && (!theStack.isEmpty()))
{
curr = theStack.pop();
currRow = curr.getRow();
currCol = curr.getCol();
//check neighbouring positions
east = maze[currRow][currCol+1];
south = maze[currRow+1][currCol];
west = maze[currRow][currCol-1];
north = maze[currRow-1][currCol];
//searching clockwise
//setting visited positions to '.', open = '0', wall = '1', exit==goal = 'e'
if(isValidPosition(east))
{
if(east.getLetter() == 'e')
{
east.setPosition(curr);
theStack.push(east.getPosition());
foundGoal = true;
}
else if((!foundGoal)&&(east.getLetter() == '0')&& (east.getLetter() != '.'))
{
east.setLetter('.');
east.setPosition(curr);
theStack.push(east.getPosition());
}
}
else if(isValidPosition(south))
{
if(south.getLetter() == 'e')
{
south.setPosition(curr);
theStack.push(south.getPosition());
foundGoal = true;
}
else if((!foundGoal)&&(south.getLetter() == '0')&& (south.getLetter() != '.'))
{
south.setLetter('.');
south.setPosition(curr);
theStack.push(south.getPosition());
}
}
else if(isValidPosition(west))
{
if(west.getLetter() == 'e')
{
west.setPosition(curr);
theStack.push(west.getPosition());
foundGoal = true;
}
else if((!foundGoal)&&(west.getLetter() == '0')&& (west.getLetter() != '.'))
{
west.setLetter('.');
west.setPosition(curr);
theStack.push(west.getPosition());
}
}
else if(isValidPosition(north))
{
if(north.getLetter() == 'e')
{
north.setPosition(curr);
theStack.push(north.getPosition());
foundGoal = true;
}
else if((!foundGoal)&&(north.getLetter() == '0')&& (north.getLetter() != '.'))
{
north.setLetter('.');
north.setPosition(curr);
theStack.push(north.getPosition());
}
}
}//end while
}
public void displayMaze()
{
for (int i = 0; i < maze.length; i++)
{
for (int j = 0; j < maze[i].length; j++)
{
maze[i][j].printElement();
}
System.out.println();
}
System.out.println("start is at " + start.getPosition());
System.out.println("exit is at " + exit.getPosition());
}//displayMaze()
public boolean isValidPosition(MazeElement element)
{
char wall = '1';
return (element.getLetter() != wall);
}
}
//**********************************
//*******Stack<E> class*************
//**********************************
class Stack<E>
{
protected Node<E> head;
public Stack()
{
head = null;
}
public boolean isEmpty()
{
return (head == null);
}
public void push(E item)
{
head = new Node<E>(item, head);
}
public E top()
{
E topItem = null;
if (head != null) topItem = head.getData();
return topItem;
}
public E pop()
{
E topItem = top();
if (head != null) head = head.getNext();
return topItem;
}
}
//**********************************
//*******Node class*****************
//**********************************
class Node <E>
{
private E data;
private Node<E> next;
public Node ()
{
//initializing everything to null at first
next = null;
data = null;
}
public Node(E data, Node <E> n)
{
this.data = data;
this.next = n;
}
public E getData()
{
return data;
}
public Node <E> getNext()
{
return next;
}
public void setNext(Node <E> next)
{
this.next = next;
}
}
我的输入文件如下：
6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
当我调用backTrack（）方法后打印迷宫时，我的迷宫（具有m和e位置）变为：
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 . 0 0 1
1 1 1 1 1
start is at 3, 1
exit is at 1, 3
问题是，我不明白为什么我的咖喱没有超越要点在输出中。请帮忙？
此处：
if(isValidPosition(east))
{
if(east.getLetter() == 'e')
{
east.setPosition(curr);
theStack.push(east.getPosition());
foundGoal = true;
}
else if((!foundGoal)&&(east.getLetter() == '0')&& (east.getLetter() != '.'))
{
east.setLetter('.');
theStack.push(east.getPosition());
}
}
原件：据我所知，唯一被推入theStack的是start。因此，curr==start。然后，在你的条件下，如果它符合你所做的方向：
east.setPosition(curr);theStack.push(east.getPosition());
（或者它测试的方向，在这种情况下实际上是南方）。
请记住，第一次curr==start，所以您正在设置east.setPosition == curr == start，这意味着您将推回到堆栈start。
现在，代码再次运行，theStack中只有一个东西，它和以前一样，只是开头下面的字符现在是"."，因此没有有效的方向，并且您的while循环中断。
要修复代码，您必须将值为方向的Position推送到theStack，而不是更新方向位置。
我对代码做了一些更改，首先是对映射加载函数，这样每个元素都有一个位置。你可以去掉这个并使用rheStack.push(new Position(row,col));，但我太懒了。
for(int row = 0; inLine != null && row < numRows; row++)
{
inLine = inFile.readLine();
tokens = inLine.trim().split("\s+");
for(int col = 0; col < numCols; col++)
{
maze[row][col] = new MazeElement(tokens[col].charAt(0),new Position(row,col));
}
}
下一个变化是回溯代码。现在，从本质上讲，您可以只使用堆栈进行回溯，但仅仅存储您去过的地方是不够的。例如，如果你先往东，然后往西，那么你也需要把它存储在堆栈上。这使得回溯变得更加复杂，然而编程语言为我们提供了一种更容易处理堆栈的方法——递归。
传递给函数的所有参数，以及它创建的所有临时性，都存储在一个特殊的堆栈上——程序堆栈。这与StackOverflow中引用的堆栈相同。因此，递归函数具有与回溯算法相同的结构。
所以我破坏了你的回溯算法，使其递归
public void backTracking()
{
Stack<Position> theStack = new Stack<Position>();//initialise stack
theStack.push(start);
//pass it the stack and the goal
backTrackingRecursive(theStack, exit);
}
public boolean backTrackingRecursive(Stack<Position> theStack, Position goal)
{
//displayMaze();
Position curr = theStack.top();
int currRow = curr.getRow();
int currCol = curr.getCol();
//setting visited positions to '.', open = '0', wall = '1', exit==goal = 'e'
for(int i = 0; i != 4; i++)
{
//forget this code, it is only to avoid writing out north, south, etc
int col = currCol;
int row = currRow;
if(i%2 == 1)
col += ((i==1)?1:-1);
else
row += ((i==2)?1:-1);
//check it is a valid position, if not continue
if(row < 0 || row >= numRows || col < 0 || col >= numCols) continue;
MazeElement next = maze[row][col];
if(next.getLetter() == 'e')
{
theStack.push(next.getPosition());
return true;
}
else if(next.getLetter() == '0')
{
theStack.push(next.getPosition());
next.setLetter('.');
if(backTrackingRecursive(theStack,goal))
{
//success!
return true;
} else {
//try a different path
next.setLetter('0');
theStack.pop();
}
}
}
return false;
}
backTrackingRecursive函数完成了所有的工作，我们只需在继续之前将下一个位置推到堆栈上。我们甚至根本不需要堆栈，但为了简单起见，我保留了它。
输出：
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
start is at 3, 1
exit is at 1, 3
1 1 1 1 1
1 0 0 e 1
1 1 1 . 1
1 m 1 . 1
1 . . . 1
1 1 1 1 1
start is at 3, 1
exit is at 1, 3
这非常有效！！！！我按照第一个答案的注释找到了这个解决方案！谢谢@CreationEdge
if(isValidPosition(east))
{
if(east.getLetter() == 'e')
{
foundGoal = true;
}
if((!foundGoal)&&(east.getLetter() == '0')&& (east.getLetter() != '.'))
{
east.setLetter('.');
east.setPosition(curr);
theStack.push(new Position(curr.getRow(), curr.getCol()+1));
}
}
if(isValidPosition(south))
{
if(south.getLetter() == 'e')
{
System.out.println(south.getLetter());
foundGoal = true;
}
if((!foundGoal)&&(south.getLetter() == '0')&& (south.getLetter() != '.'))
{
south.setLetter('.');
south.setPosition(curr);
theStack.push(new Position(curr.getRow() + 1, curr.getCol()));
}
}
if(isValidPosition(west))
{
if(west.getLetter() == 'e')
{
foundGoal = true;
}
if((!foundGoal)&&(west.getLetter() == '0')&& (west.getLetter() != '.'))
{
west.setLetter('.');
west.setPosition(curr);
theStack.push(new Position(curr.getRow(), curr.getCol()-1));
}
}
if(isValidPosition(north))
{
if(north.getLetter() == 'e')
{
foundGoal = true;
}
if((!foundGoal)&&(north.getLetter() == '0')&& (north.getLetter() != '.'))
{
north.setLetter('.');
north.setPosition(curr);
theStack.push(new Position(curr.getRow() - 1, curr.getCol()));
}
}