Given a grid maze similar to the following design an algorit

Given a grid maze similar to the following: design an algorithm and give the pseudo code to step through the maze starting at position (1, 1) and get to position (xMax -1, Max -1) Remember to keep it generic, so don\'t use the example\'s dimensions in favor of xMax and yMax. Show that your algorithm works by tracing its steps, using the example maze for your demonstration. \'robot\' knowa x,y position and facing North, South East, or Weet) Commands given in class: is Wall In Front (abbreviated is Wall) returns T if there is a wall in the next space in the facing direction, otherwise F at Destination returns T if x_2y --position (xMax-1_2y Max-1), otherwise F turn Left (abbreviated TL changes facing 90 degrees counter-clockwise turn Right abbreviated TR) changes facing 90 degrees clockwise. move Forward abbreviated Move or Step) changes the position by 1 in the facing direction. if (condition If the condition is true, do what is in the brackets, no loopback. while (condition) If the condition is true, do what is in the brackets and loopback.

Solution

Answer:

import java.io.*;

public class DetectedShortestPathInMaze
{
  
   static int number_of_rows=10;       static    int number_of_columns=10;
   static int begin_of_row=5;       static int begin_of_coloumn=3;
static int end_of_row=1;       static int end_of_coloumn=6;
  
   static    int taken_maze[][]={{1,1,1,1,1,1,1,1,1,1},
                           {1,0,0,1,0,0,0,1,0,1},
                           {1,0,1,1,1,0,1,1,0,1},
                           {1,0,0,0,0,0,0,0,0,1},
                           {1,0,1,0,1,1,0,1,1,1},
                           {1,0,0,0,0,1,0,0,0,1},
                           {1,0,1,1,1,0,0,1,1,1},
                           {1,0,1,1,1,1,0,1,0,1},
                           {1,0,0,0,0,0,0,0,0,1},
                           {1,1,1,1,1,1,1,1,1,1}};

  
   static    int shortestpath[]=new int[number_of_rows*number_of_columns];
   static    int length_short;

  
  
boolean visitedalready(int row, int col, int detectedpathsofar[], int detectedlengthsofar){
      
         
       int x;
       int goal = row*number_of_columns+col;

       for (x=0;x<detectedlengthsofar;x++)
           if (detectedpathsofar[x]==goal) return true;

       return false;
   }

  
  
   public void displayupdatedpath(int takenpath[], int takenlength){
      

       int r,c;

       for (r=0;r<number_of_rows;r++){
           for(c=0;c<number_of_columns;c++){
               if (taken_maze[r][c]==1)
                   System.out.print(\"|\");             
               else if (r==begin_of_row && c==begin_of_coloumn)
                   System.out.print(\"S\");             
               else if (r==end_of_row && c==end_of_coloumn)
                   System.out.print(\"X\");             
               else if (visitedalready(r,c,takenpath,takenlength))
                   System.out.print(\"o\");             
               else
                   System.out.print(\" \");             
           }
           System.out.println(\"\");
       }
   }
  
   public void searchnewpath(int row, int col, int detectedpathsofar[], int detectedlengthsofar){
      

      
       if (row<0 || col<0 || row>=number_of_rows || col>=number_of_columns)
           return;
       if (taken_maze[row][col]==1) return ;
       if (visitedalready(row, col, detectedpathsofar, detectedlengthsofar)) return;

       int takenpath[]=new int[detectedlengthsofar+1];

       System.arraycopy(detectedpathsofar, 0, takenpath, 0, detectedlengthsofar);
          
                          
      
       takenpath[detectedlengthsofar++]=row*number_of_columns+col;

       if (row==end_of_row && col==end_of_coloumn){      
          

           System.out.println(\"Detected path of length \"+detectedlengthsofar+\":\");
           displayupdatedpath(takenpath, detectedlengthsofar);

           if (detectedlengthsofar<=length_short){
               length_short=detectedlengthsofar;
               System.arraycopy(takenpath, 0, shortestpath, 0, detectedlengthsofar);
               System.out.println(\" The new shortest path is of length \" + detectedlengthsofar);
           }
           System.out.println(\"\");
           return;
       }

      
       searchnewpath(row-1, col, takenpath, detectedlengthsofar);
       searchnewpath(row, col-1, takenpath, detectedlengthsofar);
       searchnewpath(row, col+1, takenpath, detectedlengthsofar);
       searchnewpath(row+1, col, takenpath, detectedlengthsofar);
   }
          
  
   public static void main(String[] args)
   {
      

       int r,c,x;              
       int detectedpathsofar[];      
       int detectedlengthsofar;      

       DetectedShortestPathInMaze obj=new DetectedShortestPathInMaze();  

       detectedpathsofar=new int[obj.number_of_rows*obj.number_of_columns];
      
       for (x=0;x<obj.number_of_rows*obj.number_of_columns;x++){
           obj.shortestpath[x]=-1;
           detectedpathsofar[x]=-1;
       }

      
       obj.length_short=obj.number_of_rows*obj.number_of_columns+1;
       detectedlengthsofar=0;

       System.out.println(\"The Maze Is Shown As Below:\");
       for (r=0;r<obj.number_of_rows;r++){
           for (c=0;c<obj.number_of_columns;c++){
               if (r==begin_of_row && c==begin_of_coloumn)      
                   System.out.print(\"S\");      
               else if (r==end_of_row && c==end_of_coloumn)
                   System.out.print(\"x\");
               else if (obj.taken_maze[r][c]==0)
                   System.out.print(\" \");
               else System.out.print(\"|\");
           }
           System.out.println(\"\");
       }

       System.out.println(\"\");
       System.out.println(\"Searching For Paths!!!!!\");

       obj.searchnewpath(begin_of_row, begin_of_coloumn, detectedpathsofar, detectedlengthsofar);

       System.out.println(\"\");
       System.out.println(\"The shortest path was found with the following of length \"+ obj.length_short);
       obj.displayupdatedpath(obj.shortestpath, obj.length_short);

   }
}