C CODE Consider a 2D array of 1s and 0s of size NxN The arra

[C++ CODE ]Consider a 2D array of 1s and 0s of size NxN. The array is a \"maze.\" You must start from the top left (index (0,0)) and find the length of the shortest path to the bottom right (index (n,n)). You may only travel across elements that have value \"1\". The top left and bottom right indices are guaranteed to be \"1\". You may only move horizontally or vertically one index position with each step.

For example, for the following input maze, a shortest path is along bolded numbers and has a length of 8:

11001

01011

01100

11110

11011

Your program will open an input file, called maze.txt, containing a maze. Your program should be executed with no command-line arguments, read the provided maze from the file, determine N, the dimension of the maze, and output the length of the shortest path to the screen. If no path exists, your program should output ‘0’. You may use the provided maze.txt file to test your code.

Submit your code, along with a modified makefile that can be used to compile and run your code on the lab computers.

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,0,0,1},
{0,1,0,1,1},
{0,1,1,0,0},
{1,1,1,1,0},
{1,1,0,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);

   }
}