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

Check if the current position is valid:
- Is it within the bounds of the maze?
- Is it an open path or the exit?
Check if the current position is 'E'. If yes, return true.
Mark the current cell as visited (change it to '#').
Recursively explore all possible directions (up, down, left, right).
If any direction leads to the exit, return true.
Restore the cell to ' ' after exploring (backtracking).
If no paths lead to the exit, return false.

Test Case 2: Starting at the Exit


char[][] maze = {
    {'#', '#', '#', '#', '#'},
    {'#', ' ', ' ', '#', 'E'},
    {'#', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', '#'},
    {'#', '#', '#', '#', '#'}
};

System.out.println(solveMaze(maze, 1, 4)); // Output: true