// Mole.h


// IEEE Challenge 13 - The Hard Life Of A Mole

// http://www.ieee.org/portal/cms_docs_iportals/iportals/membership/

//       /students/scholarshipsawardscontests/

//       /IEEEXtreme2008_Competitition_book_2.pdf


// by Adrian Dale 15/12/2008 / 26/07/2009

#pragma once


#include "boost/multi_array.hpp"

#include <vector>

#include <stack>


using namespace std;


// Struct to hold coords of a position on our grid.

struct Move


      Move():x(0),y(0) {}

      Move(int xi, int yi):x(xi),y(yi) {}

      int x;

      int y;



typedef vector<Move> MoveListType;


typedef char MapDataCellType;

typedef boost::multi_array<MapDataCellType, 2> MapDataType;


// A WorkingMapCell holds per cell info that we need for our

// solving algorithm

class WorkingMapCell



      WorkingMapCell() : mCostToStart(0), mVisited(false)

                              { mCheapestMove.x = 0; mCheapestMove.y = 0; }

      ~WorkingMapCell() {}


      // What's at this cell

      MapDataCellType mCell;

      inline void SetCell(MapDataCellType squ) {mCell = squ;}


      // Cost to travel from this cell to the start

      int mCostToStart;

      // Cheapest direction to start

      Move mCheapestMove;

      // Has our algorithm checked this cell yet?

      bool mVisited;

      inline void SetVisited(bool visited) {mVisited = visited;}




typedef boost::multi_array<WorkingMapCell, 2> WorkMapDataType;


typedef stack<Move> MoveStackType;


// This class holds our map and provides operations on it.

class Underground



      // Solve() calls separate functions so that we can break the solution

      // down into steps for display on our window in the GUI version

      // It will return -1 if it needs to be called again, otherwise it returns

      // the cost of the cheapest solution.

      int Solve();


      // What does a move to square x,y cost?

      // (Tunnels are 0, soil is 1, etc)

      int MoveCost(int x, int y) const;


      // What is at square x,y?

      inline MapDataCellType GetSquareType(int x, int y) const

                                                      {return mMapData[x][y];}


      // Locate our start/end points

      Move FindSquare( MapDataCellType squType ) const;


      // Standard row/column accessor functions

      inline int GetRowCount() const { return mRows; }

      inline int GetColumnCount() const { return mCols; }


#ifdef _DEBUG

      // Used for debugging - dumps to stdout, which isn't much

      // use for our windows app

      void DumpMap() const;




      // ReadInput reads our map data from stdin

      void ReadInput();


      // Set up the map ready to be solved

      void Solve_Init();    

      // Perform a first pass of the solution

      void Solve_FirstPass();

      // Code used by Solve_FirstPass that is called for each

      // direction away from the square we need to check

      void ProcessDirection(MoveStackType &moveStack, int x, int y);

      // Refine our initial cut of the solution

      int RescanCheapest();

      // Code called for each direction from the square

      // currently being scanned.

      bool RescanCheapestCell(WorkingMapCell * workCell,

                        WorkingMapCell * neighbourCell, int x, int y, int xx, int yy);


      // Calculates the cost of the cheapest route by walking back from B to A,

      // and summing up the costs once that route is known.

      int SolutionCost();


      int mRows;

      int mCols;


      // Cache this info so we don't need to keep asking for it

      Move mStartPos;

      Move mEndPos;


      // Our map data, as read from the file

      MapDataType mMapData;


      // Copy of the map used by our solver to solve the puzzle

      WorkMapDataType mWorkMap;