Homework

Team Teach Homework

Maze Solver Problem

Instructions

Your task is to write a method solveMaze(char[][] maze, int startX, int startY) that determines whether a path exists from a starting point (startX, startY) in a 2D maze to the exit marked as 'E'. Use recursion to explore the maze.

---

Requirements

Input

• A 2D array of characters (char[][] maze) representing the maze.

• An integer startX indicating the row index of the starting point.

• An integer startY indicating the column index of the starting point.

Output

• Return true if there is a path from (startX, startY) to 'E'.

• Return false if no such path exists.

Maze Rules

• ' ' represents an open path (you can move here).

• '#' represents a wall (you cannot move here).

• 'E' represents the exit (this is the destination).

Movement

• You can move up, down, left, or right to adjacent cells.

• You cannot move diagonally or leave the bounds of the maze.

Marking Visited Cells

• To avoid revisiting the same cells, mark visited cells as '#' temporarily during recursion. Restore them to ' ' after backtracking.

---

Steps to Solve

1. Check if the current position is valid:

   • Is it within the bounds of the maze?

   • Is it an open path or the exit?

2. Check if the current position is 'E'. If yes, return true.

3. Mark the current cell as visited (change it to '#').

4. Recursively explore all possible directions (up, down, left, right).

5. If any direction leads to the exit, return true.

6. Restore the cell to ' ' after exploring (backtracking).

7. If no paths lead to the exit, return false.

---

// Test Case 2: Starting at the Exit

public class Main {

    public static boolean solveMaze(char[][] maze, int row, int col) {
        // ok so this is our first base case: if we've gone out of bounds or hit a wall, return false
        if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length || maze[row][col] == '#') {
            return false;
        }

        // second base case: if we reach the exit, return true
        if (maze[row][col] == 'E') {
            return true;
        }

        // mark current cell as visited (I decided to mark it as a wall so we don't visit it again since we can't go to walls)
        maze[row][col] = '#';

        // try going all directions and see if we can find a path
        boolean foundPath = solveMaze(maze, row - 1, col) || // up
                            solveMaze(maze, row + 1, col) || // down
                            solveMaze(maze, row, col - 1) || // left
                            solveMaze(maze, row, col + 1);   // right

        // after we recurse, we need to backtrack, so we mark this cell as no longer being visited
        maze[row][col] = ' ';

        return foundPath; // return whether we found a valid path in either of the 4 directions

    }

    public static void main(String[] args) {
        char[][] maze1 = {
            {'#', '#', '#', '#', '#'},
            {'#', ' ', ' ', '#', 'E'},
            {'#', ' ', '#', ' ', '#'},
            {'#', ' ', ' ', ' ', '#'},
            {'#', '#', '#', '#', '#'}
        };
        char[][] maze2 = {
            {'#', '#', '#', '#', '#'},
            {'#', ' ', '#', '#', 'E'},
            {'#', ' ', '#', '#', '#'},
            {'#', ' ', ' ', ' ', '#'},
            {'#', '#', '#', '#', '#'}
        };
        char[][] maze3 = {
            {'#', '#', '#', '#', '#'},
            {'#', ' ', ' ', ' ', 'E'},
            {'#', ' ', '#', ' ', '#'},
            {'#', ' ', ' ', ' ', '#'},
            {'#', '#', '#', '#', '#'}
        };


        System.out.println("Testcase 1: " + solveMaze(maze1, 1, 4)); // Output: true
        System.out.println("Testcase 2: " + solveMaze(maze2, 3, 1)); // Output: false
        System.out.println("Testcase 3: " + solveMaze(maze3, 1, 1)); // Output: true
    }
}

Main.main(null);

Testcase 1: true
Testcase 2: false
Testcase 3: true