Java related. If you can\'t see the image, right-click and go to view image to z

Question

Java related. If you can't see the image, right-click and go to view image to zoom in

You are currently located inside a maze, at the position marked with a period (.). The walls of the maze are indicated by asterisks (*). The character 'e' denotes the exit. The character V Indicates the starting position. e denotes exit Make sure to include in test data Use the following recursive approach to escape from the maze: Try moving in each of the four possible directions. If you found an exit, return true. If you found a wall or a position that you have previously visited, return false. If you found an empty spot, mark it as a period, and recursively call the escape method again. This method merely tests whether there is a path out of the maze. The program should work from any starting position. Test your program to make sure it works in all cases including the two test cases above.

Explanation / Answer

/* -> If prints all the paths from source to exit
* -> If no path is found, then it returns false and prints the message
*/

public class Maze {
  
    /**
     * U - Up
     * D - Down
     * L - Left
     * R - Right
     * */
    public static char[] direction = {'U','D', 'L','R'};

    /**
     * Keeps track of the path from source to current cell
     */
    public static char path[];
    public static int end = -1;
  
    /**
     * Offsets for neighbouring vertices
     */
    public static int[] xNeigh = {-1, 1, 0, 0};
    public static int[] yNeigh = {0, 0, -1, 1};  
  
  
    public static void run(char[][] A, int m, int n) {
        path = new char[m*n];
        int[][] visited = new int[m][n];
     
        /* Find the source node in the matrix */
        int x = -1;
        int y = -1;
        for (int i=0; i<m; i++) {
           for (int j=0; j<n; j++) {
               if (A[i][j] == '.') {
                   x = i; y=j;
                   break;
               }
           }
        }
        if (x==-1 || y==-1) {
           return;
        }
      
        boolean result = DFS(A, m, n, x, y, visited);
        if (!result) {
           System.out.println("Err : Path Not Found!");
        }
     }
   
    public static boolean DFS(char[][] A, int m, int n, int i, int j, int[][] visited) {
      
       /* If the exit is reached
          * */
         if (A[i][j] == 'e') {
             printPath();
             return true;
         }
       
         /* Mark the current cell as visited */
         visited[i][j] = 1;
         boolean result = false;
       
         for (int k=0; k<4; k++) {
             if (isSafe(A, m, n, i+xNeigh[k], j+yNeigh[k], visited)) {
               path[++end] = direction[k];
                 result = DFS(A, m, n, i+xNeigh[k], j+yNeigh[k], visited);
                 end--;
             }
         }
       
         /* Unmark the current node, so trace other paths */
         visited[i][j] = 0;
         return result;
     }
   
      public static boolean isSafe(char[][] A, int m, int n, int i, int j, int[][] visited) {
        if (i>=0 && i<m && j>=0 && j<n && visited[i][j] == 0 && A[i][j]!='*') {
            return true;
        }
        return false;
      }    
    
      public static void printPath() {
          for (int i=0; i<end; i++) {
              System.out.print(path[i] +"->");
          }
          System.out.println(path[end]);
      }
    
      public static void main(String args[]) {

          char A[][]= new char[][] {{'*', '*', '*', '*', '*', '*', '*', '*', '*'},
                                     {'*', ' ', ' ', ' ', ' ', ' ', '*', ' ', '*'},
                                     {'*', ' ', '*', '*', '*', '*', '*', ' ', '*'},
                                     {'*', ' ', '*', ' ', '*', ' ', ' ', ' ', '*'},
                                     {'*', ' ', '*', ' ', '*', '*', '*', ' ', '*'},
                                     {'*', ' ', ' ', ' ', '.', ' ', ' ', ' ', '*'},
                                     {'*', '*', '*', ' ', '*', ' ', '*', ' ', '*'},
                                     {'*', ' ', ' ', ' ', ' ', ' ', '*', ' ', '*'},
                                     {'*', '*', '*', '*', '*', '*', '*', 'e', '*'}};
           run(A, 9, 9);                     
      }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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