MazeSolver.java

/* Uses a DFS to find a path in the maze from start to end
   and returns the path as a list of Cell objects.

MazeSolver.java
*/

import java.util.*;

public class MazeSolver {
    private final Maze maze;
    
    // Constructor for MazeSolver class that takes a Maze object
    public MazeSolver(Maze maze) {
        this.maze = maze;
    }

    // Solve the maze using DFS algorithm
    // Returns a list of Cells for the path from start to end
    public List<Cell> solveDFS(Cell start, Cell end) {
        int totalCells = maze.rows * maze.cols;
        boolean[] visited = new boolean[totalCells];
        int[] parent = new int[totalCells]; 
        
        // Initialize parent array
        for (int i = 0; i < totalCells; i++) {
            parent[i] = -1;
        }

    // Convert start and end cells to their respective locations
    int startLocation = maze.location(start.row, start.col); 
    int endLocation = maze.location(end.row, end.col);

        // Create a stack for DFS
        Deque<Integer> stack = new ArrayDeque<>();
    stack.push(startLocation);
    visited[startLocation] = true;

        // The actual DFS loop
        // Perform DFS until stack is empty or end is found
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            if (cur == endLocation) break;

            List<Integer> neighbors = maze.adj.get(cur);
            
            // Check all neighbors
            // For each neighbor, if not visited, mark visited, set parent, and push to stack
            for (int i = 0; i < neighbors.size(); i++) { 
                int currentNei = neighbors.get(i);

                // If neighbor not visited
                if (!visited[currentNei]) {
                    visited[currentNei] = true;
                    parent[currentNei] = cur; 
                    stack.push(currentNei);
                }
            }
        }

    if (!visited[endLocation]) return null; // If no path found

        // Path reconstruction
        // Backtrack from end to start using parent array
        List<Cell> path = new ArrayList<>();
    int p = endLocation;
        while (p != -1) {
            int r = p / maze.cols; // Local variable r is fine here
            int c = p % maze.cols; // Local variable c is fine here
            path.add(maze.grid[r][c]); // Accesses the grid
            p = parent[p]; 
        }

        Collections.reverse(path); // Reverse to get path from start to end
        return path;
    }
}