PathValidator.java

public class PathValidator {
    private char[][] grid;
    private boolean[][] visited;
    private int rows, cols;
    private int startRow, startCol;

    public PathValidator(char[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];
        findStart();
    }

    private void findStart() {
        // Locate the first start cell and use it as the DFS entry point.
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 'S') {
                    startRow = i;
                    startCol = j;
                    return;
                }
            }
        }
    }

    public boolean pathExists() {
        return dfs(startRow, startCol);
    }

    private boolean dfs(int r, int c) {
        // Stop recursion when coordinates are outside the grid.
        if (r < 0 || c < 0 || r >= rows || c >= cols) {
            return false;
        }

        // Walls and already visited cells cannot be part of a valid path.
        if (grid[r][c] == '1' || visited[r][c]) {
            return false;
        }

        // Reaching the end cell means a valid path exists.
        if (grid[r][c] == 'E') {
            return true;
        }

        visited[r][c] = true;

        // Explore all four directions (down, up, right, left).
        return dfs(r + 1, c) ||
                dfs(r - 1, c) ||
                dfs(r, c + 1) ||
                dfs(r, c - 1);
    }
}