// Maze class
// Login(s):
// Date:

import java.util.ArrayList;

/*
 * File for conducting a breadth first search (BFS) in a 2D grid. 
 */
class Maze {

	/*
	 * data member for the Maze class... a 2d rectangular array of MazeCells
	 */
	MazeCell[][] mazeContents2D; //

	// MazeCell - an inner class supporting Maze
	//
	// The following convention is used in mazes:
	// Walls are represented by '*'
	// Empty area is represented by the blank symbol ' '
	// Starting point is represented by 'S'
	// Destination (SPAM!) is represented by 'D'
	class MazeCell {
		private int row; // The row at which this cell is located
		private int col; // The col at which this cell is located
		private char contents; // Each cell has contents (a char)
		private boolean visited; // A cell can be marked as visited.
		private MazeCell parent; // parent is where we came from!

		/*
		 * Constructor of the MazeElement at row, col, with contents c "visited"
		 * is set to false, and "parent" is set to null
		 */
		private MazeCell(int row, int col, char c) {
			this.row = row; // this is required to avoid name confusion!
			this.col = col; // ditto
			this.contents = c;
			this.visited = false; // we haven't been here yet...
			this.parent = null; // ... so we have no parent yet
		}

		/*
		 * toString()
		 * 
		 * method called when a MazeCell is passed as an arugment to
		 * System.out.println
		 */
		public String toString() {
			return "[" + row + "," + col + "," + contents + "]";
		}

		/*
		 * isWall()
		 * 
		 * @return true if the current MazeCell is a wall (represented with *)
		 */
		public boolean isWall() {
			return this.contents == '*';
		}
	}

	/*
	 * 
	 */
	public Maze(int height, int width, String mazeText) {
		char[] mazeContents = mazeText.toCharArray();
		// create the maze cell references ... but not the MazeCells
		// themselves
		mazeContents2D = new MazeCell[height][width]; // all of the MazeCells
														// are null!!
		for (int r = 0; r < mazeContents2D.length; r++) { // loop over the rows
			for (int c = 0; c < mazeContents2D[r].length; c++) { // loop over
																	// the
																	// columns
				char ch = mazeContents[r * width + c];
				mazeContents2D[r][c] = new MazeCell(r, c, ch);
			}
			// now the MazeElements are not null...
		}
	}

	/*
	 * the findMazeCell method takes the maze and a char token (either 'S' or
	 * 'D') and returns the MazeElement containing the location of that token in
	 * the maze.
	 */
	public MazeCell findMazeCell(char charToFind) {
		for (int r = 0; r < mazeContents2D.length; r++) {
			for (int c = 0; c < mazeContents2D[r].length; c++) {
				if (mazeContents2D[r][c].contents == charToFind) {
					return mazeContents2D[r][c];
				}
			}
		}
		return null; // Error in finding the charToFind: it's not there!
	}

	/*
	 * BFS(MazeCell start, MazeCell destination)
	 * 
	 * @param start is the MazeCell to begin the breadth first search from
	 * 
	 * @param destination is the MazeCell to end the breadth first search at
	 * 
	 * @return an ArrayList<String> representing the path from the start
	 * MazeCell to the destination MazeCell. If there is no path, null should be
	 * returned instead. A single element of the path should be represented like
	 * this example: (r=2,c=1)
	 * 
	 * This method modifies the contents of the Maze object. When the method
	 * ends, each reachable empty (' ') MazeElement should have its "parent"
	 * data member set to the MazeElement from which it was visited. All
	 * MazeCells along the path should be represented by the character 'o'
	 */
	public ArrayList<String> BFS(MazeCell start, MazeCell destination) {
		// TODO: Write the BFS method
		
		/*
		 * Here is some code demonstrating how to make a Queue and
		 * ArrayList<String> etc.
		 */
		
		// You'll need a Queue, but can name it whatever you like.
		Queue mazeCellsToExplore = new Queue(); 
		 // You'll need an ArrayList<String> to return your answer.
		ArrayList<String> path = new ArrayList<String>();
		
		// Example of how you add something to the start of an ArrayList
		int row = 3;
		int col = 4;
		path.add(0, "(r=" + row + ",c=" + col + ")"); 

		// Return null if you don't find a path, otherwise return the ArrayList.
		return null;
	}

	/*
	 * getPath()
	 * 
	 * @return an ArrayList<String>.
	 * 
	 * This method calls the BFS method with the start and destination MazeCells.
	 */
	public ArrayList<String> getPath(){
		MazeCell start = this.findMazeCell('S'); // get the Source
		MazeCell destination = this.findMazeCell('D'); // get the Destination
														// (SPAM!)
		return this.BFS(start, destination);
		
	}
	/*
	 * toString
	 * 
	 * @return the String representation of the maze
	 */
	public String toString() {
		String result = "\n";
		for (int r = 0; r < mazeContents2D.length; ++r) {
			for (int c = 0; c < mazeContents2D[r].length; ++c) {
				result += mazeContents2D[r][c].contents;
			}
			result += "\n";
		}
		result += "\n";
		return result;
	}

	/*
	 * You may chose to do additional debugging in the main method
	 */
	public static void main(String args[]) {
		ArrayList<String> x = new ArrayList<String> ();
		x.add("1");
		x.add("2");
		x.add("3");
		x.add("4");
		System.out.println(x);
	}

}