import java.awt.Color;
import java.util.ArrayList;

/**
 * thePath class that implements the interface MazeSolver using recursion
 * @author Bill Kraynek
 */
public class RecursiveMazeSolution implements MazeSolver {

    public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
        boolean[][] marked;
        marked = new boolean[maze.getRows()][maze.getColumns()];
        return getPath(startRow, startCol, finishRow, finishCol, maze,marked);
    } // end solveMaze

    ArrayList<Maze.Door> getPath(int row, int col, int finishRow, int finishCol, Maze maze,boolean[][] marked) {
        marked[row][col] = true;
        // base case
        if (row == finishRow && col == finishCol) {
            ArrayList<Maze.Door> thePath = new ArrayList<Maze.Door>();
            thePath.add(new Maze.Door(row, col, Maze.NO_DIRECTION, Color.RED));
            return thePath;
        } // end if
        // try East
        if (!maze.isClosed(row, col, Maze.EAST) && !marked[row][col + 1]) {
            ArrayList<Maze.Door> thePath = getPath(row, col + 1, finishRow, finishCol, maze, marked);
            if (thePath != null) {
                thePath.add(0, new Maze.Door(row, col, Maze.EAST, Color.RED));
                return thePath;
            }
        } // end if
        //try South
        if (!maze.isClosed(row, col, Maze.SOUTH) && !marked[row + 1][col]) {
            ArrayList<Maze.Door> thePath = getPath(row + 1, col, finishRow, finishCol, maze, marked);
            if (thePath != null) {
                thePath.add(0, new Maze.Door(row, col, Maze.SOUTH, Color.RED));
                return thePath;
            }
        } // end if
        // try West
        if (!maze.isClosed(row, col, Maze.WEST) && !marked[row][col - 1]) {
            ArrayList<Maze.Door> thePath = getPath(row, col - 1, finishRow, finishCol, maze, marked);
            if (thePath != null) {
                thePath.add(0, new Maze.Door(row, col, Maze.WEST, Color.RED));
                return thePath;
            }
        } // end if
        // try North
        if (!maze.isClosed(row, col, Maze.NORTH) && !marked[row - 1][col]) {
            ArrayList<Maze.Door> thePath = getPath(row - 1, col, finishRow, finishCol, maze, marked);
            if (thePath != null) {
                thePath.add(0, new Maze.Door(row, col, Maze.NORTH, Color.RED));
                return thePath;
            }
        }
        // failure
        return null;
    } // end getPath
} // end MazeSolution