/***
 * TODO: Fill in your name, lab section, lecture section, etc etc.
 * Also note the purpose of the program.
 *
 *
 */

#include <iostream>
#include "point.h"
#include "mazequeue.h"

using namespace std;


/**
 * Function predeclarations
 *
 */

// This function takes in the maze as a 2 dimensional array, the 
// width and height of that array, and the starting and ending points.
// It then finds a minimal length path from start to dest, fills in
// that path with 'X's, and returns.
void solve(MazeElement** maze, int width, int height, Point start, Point dest);

// This function takes in a maze and a point. If that point was 
// visited from somewhere, fill in the visitor with a 'X'.  Repeat
// this process until we find something we can't track back through.
void backtrack(MazeElement** maze, int width, int height, Point dest);

// This function prints out the contents of a maze
void printMaze(MazeElement** maze, int width, int height);


// The main function, obviously.
// DO NOT ALTER THIS FUNCTION.
int main(int argc, char** argv)
{
  // The maze iteself
  MazeElement** maze;

  // Used as a temp for reading in the maze
  string cur;

  // The dimensions of the maze.  We'll get these from the first line
  // of the maze input
  int width;
  int height;

  // Which row we are filling in right now
  int row;

  // Set these to coordinates that are obviously wrong so we can check
  // to make sure that we found them in the input
  Point start(-1, -1);
  Point dest(-1, -1);

  // Get width and height
  cin >> width;
  cin >> height;
  
  // Allocate space for the maze
  maze = new MazeElement*[height];
  for (int i = 0; i < height; i++)
    {
      maze[i] = new MazeElement[width];
    }

  // Now we call getline once to get rid of the extra "\n" lurking 
  // in the stream
  getline(cin, cur);
  
  // Now get the first line
  getline(cin, cur);

  // Now fill in the maze
  row = 0;
  while (cin)
    {
      // If for some reason the maze is mal-formatted, give up
      if ((int)cur.size() != width) break;
      for (int i = 0; i < width; i++)
	{
	  // Fill in the current position
	  maze[row][i].contents = cur[i];

	  // Note where we are
	  maze[row][i].location = Point(i, row);

	  // Check for the start token
	  if (cur[i] == 'S' && start.getx() == -1 && start.gety() == -1)
	    {
	      start.setx(i);
	      start.sety(row);
	    }

	  // Check for the dest token
	  else if (cur[i] == 'D' && dest.getx() == -1 && dest.gety() == -1)
	    {
	      dest.setx(i);
	      dest.sety(row);
	    }	    
	}
      // Update the next row
      row++;

      // Get the next line
      getline(cin, cur);
    }

  // Call the solver!
  solve(maze, width, height, start, dest);

  // Free up our memory
  for (int i = 0; i < height; i++)
    delete[] maze[i];
  
  delete[] maze;

}

// This function prints out the contents of a maze
// You do not need to alter this function.
void printMaze(MazeElement** maze, int width, int height)
{
  for (int i = 0; i < height; i++)
    {
      for (int j = 0; j < width; j++)
	{
	  cout << maze[i][j].contents;
	}
      cout << endl;
    }
}


// TODO: Fill in this function.
void backtrack(MazeElement** maze, int width, int height, Point dest)
{


}


// TODO: Fill in this function
void solve(MazeElement** maze, int width, int height, Point start, Point dest)
{
  // Note that MazeElement** means that maze is a two-dimensional array
  // of MazeElements.  

  // Examine the "printMaze" function to see how to access points
  // in the maze, and look through the "mazequeue.h" section to see
  // what fields are provided in a MazeElement.

  // Read Savitch Chapter 6 for more information on this.

  // Get a new Mazequeue
  // Add the start point to the Mazequeue
  // loop while something is in the queue, according to the algorithm
  //   on the course webpage.
  
}