java - 使用回溯算法测试鼠标是否可以逃离矩形迷宫

Question

该程序旨在通过读取文本文件来创建和解决鼠标从迷宫逃生的路线。有一个 Maze 类，它基本上是 MazeElements 的 2D 数组，MazeElements 包含一个 char 变量和一个位置目的; Position 保存二维数组上每个元素的坐标。 到目前为止，程序有效地读入并创建了二维数组。问题出在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

问题是我不明白为什么我的 curr 没有超出点“。”在输出中。请帮忙？

Answer 1

这里:

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 中只有 1 个内容，并且与之前相同，除了 start 下面的字符现在是“.”，因此没有有效的方向和您的 while 循环中断。

要修复代码，您必须将一个 Position 推送到 theStack ，其值为方向的值，并且不更新方向位置。