// 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

{

public:

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

{

public:

// 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;

#endif

private:

// 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;

};