Hello please help implementing the find path method to find path from the entran

Question

Hello please help implementing the find path method to find path from the entrance to the exit, using non-recursive depth-first search from the lower-left corner to the upper-right. If a path is found, mark all the cells on the route and return true. Otherwise, mark everything reachable and return false.

public class Maze {

   private final int _rows, _columns;
   private boolean[][] _ropen, _copen;
   private boolean[][] _marked;
  
   /*
   * _ropen[i,j] is true if one can get from cell [i,j] to cell [i+1,j]
   * _copen[i,j] is true is one can get from cell [i,j] to cell[i,j+1];
   */
  
   public Maze(int rows, int columns) {
       _rows = rows;
       _columns = columns;
       _ropen = new boolean[rows-1][columns];
       _copen = new boolean[rows][columns-1];
       _marked = new boolean[rows][columns];
   }
  
   public int rows() { return _rows; }
   public int columns() { return _columns; }   

public void read(BufferedReader r) throws IOException {
       // TODO: Implement this method
       try{
       String currentLine;

       int col = 0;

       while ((currentLine = r.readLine())!= null){

       if (currentLine.charAt(0)=='|'){
       _ropen[0][col] = false;
       }
       else{
       _ropen[0][col] = true;
       }
       if (currentLine.charAt(1)=='|'){
       _ropen[1][col] = false;
       }
       else{
       _ropen[1][col] = true;
       }
       if (currentLine.charAt(2)=='|'){
       _ropen[2][col] = false;
       }
       else{
       _ropen[2][col] = true;
       }
       if (currentLine.charAt(3)=='|'){
       _ropen[3][col] = false;
       }
       else{
       _ropen[3][col] = true;
       }
       col++;
       }
       int row = 0;
       while ((currentLine = r.readLine())!= null){
       if (currentLine.charAt(0)=='-'){
       _ropen[row][0] = false;
       }
       else{
       _ropen[row][0] = true;
       }
       if (currentLine.charAt(1)=='-'){
       _ropen[row][1] = false;
       }
       else{
       _ropen[row][1] = true;
       }
       if (currentLine.charAt(2)=='-'){
       _ropen[row][2] = false;
       }
       else{
       _ropen[row][2] = true;
       }
       row++;
       }
       r.close();
       }
       catch(IOException e){
       e.printStackTrace();
       }
   }

public boolean findPath()
   {

   }

public void clear() {
       for (int i = 0; i < _rows; ++i) {
           for (int j=0; j < _columns; ++j) {
               _marked[i][j] = false;
               if (i+1 != _rows) _ropen[i][j] = false;
               if (j+1 != _columns) _copen[i][j] = false;
           }
       }
   }
  
   private JComponent panel;

   public JComponent getPanel() {
       if (panel == null) panel = new Panel();
       return panel;
   }

   @SuppressWarnings("serial")
   public static class ParseException extends IOException {
       public ParseException(String s) { super(s); }
   }
  
  
   public class Cell {
       public final int row, column;
       public Cell(int i, int j) {
           if (i < 0 || i >= _rows) throw new IllegalArgumentException("row " + i + " out of range [0," + _rows + ")");
           if (j < 0 || j >= _columns) throw new IllegalArgumentException("column " + j + " out of range [0," + _columns + ")");
           this.row = i;
           this.column = j;
       }
       public String toString() {
           return "[" + row + "," + column + "]";
       }
   }

Explanation / Answer

Solution: See the code below

--------------------------------------

    public boolean findPath() {
       boolean pathFound=false; //flag to tell whether path is found or not
      
       //all cells marked as unvisited initially
       for (int i = 0; i < _rows; ++i) {
           for (int j = 0; j < _columns; ++j) {
               _marked[i][j] = false;
           }
       }
      
       //location to start search - lower left corner
       //it is assumed there will always be an open entry at lower left corner.
       int currentRow=_rows;
       int currentColumn=0;
       int previousRow=_rows+1, previousColumn=-1; //with respect to current row and columns
       //loop to find the path
       while(currentRow!=0 && currentColumn!=_columns)
       {
           if(_ropen[currentRow][currentColumn]==true)
           {
               _marked[currentRow][currentColumn]=true;
               previousRow=currentRow;
               previousColumn=currentColumn;
               currentRow=currentRow-1;
               pathFound=true;
           }
           else if(_copen[currentRow][currentColumn]==true)
           {
               _marked[currentRow][currentColumn]=true;
               previousRow=currentRow;
               previousColumn=currentColumn;
               currentColumn=currentColumn+1;
               pathFound=true;              
           }
           else //no path found, backtrack to previous position
           {
               pathFound=false;
               currentRow=previousRow;
               currentColumn=previousColumn;
           }
       }      
       return pathFound; //returns whether path is found or not.
   }

------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.