// DFS_Recursive.java

public class DFS_Recursive {
    public static boolean search(char[][] maze, int x, int y) {
        System.out.println("We are at (" + x + ", " + y + ")");

        // check if we're done
        if ((x == 17) && (y == 7)) {
            return true;
        }

        // mark this spot as seen
        maze[y][x] = 'X';

        // if we haven't gone left, and not out of bounds, go left
        if (((x - 1) >= 0) && (maze[y][x - 1] == '-'))
            if (search(maze, x - 1, y))
                return true;

        // go right
        if (((x + 1) <= 17) && (maze[y][x + 1] == '-'))
            if (search(maze, x + 1, y))
                return true;

        // go bottom
        if (((y + 1) <= 7) && (maze[y + 1][x] == '-'))
            if (search(maze, x, y + 1))
                return true;

        // go top
        if (((y - 1) >= 0) && (maze[y - 1][x] == '-'))
            if (search(maze, x, y - 1))
                return true;

        // if we got here, there was no way on this path
        return false;
    }

    public static void main(String[] args) {
        String[] mazeString = {
            "-#################",
            "----------##-----#",
            "-########-##-##-##",
            "-########----##-##",
            "-########-#####-##",
            "-----####-#####-##",
            "#########-###---##",
            "####------#####---"};

        // convert to 2D array of char
        char [][] maze = new char[8][18];
        for (int i = 0; i < mazeString.length; i++) {
            for (int j = 0; j < mazeString[i].length(); j++) {
                maze[i][j] = mazeString[i].charAt(j);
            }
        }

        if (search(maze, 0, 0)) {
            System.out.println("Done!");
        } else {
            System.out.println("No path!");
        }
    } 
}