//  POTM ENTRY:  Spelunker
//  Your Name:   Andre' Wilhelmus
//  Your email:  wilhelmus@lucent.com
//
//  Version:	 12C (960715)

#define DEBUG 0
#define DEBUG2 0
#define TEST 0
#define CHECK 0
#define CHECK2 0

#include 
#include 
#include 
#if __MWERKS__
#include 
#else
#include 
#include 
#include 
#include 
#include 
//#include 
#endif
#include 

int const false = 0;
int const true = 1;
typedef int bool;

int const MAX_TIME = 590;
	
unsigned int max_time = MAX_TIME;
int level = 0;
#if DEBUG
int debug = 0;
#endif

bool time_out = false;
bool print_score = false;
long clk_tck;			// system clock frequency

class Node;
class Edge			// a path to another room
{
public:
  Edge(){};
  Edge(Node *a_from_node, Node *a_to_node, char a_dir);
  void eval_edge();

  Node *to_node;
  Node *from_node;
  char dir;			// direction
  int value;
};

class Node			// a room
{
public:
  Node();
  void add_edge(char dir, Node *to_node);
  Edge *find_dir(char const dir);
  int get_path_length(Node *path_e);
  int pending_path_length(Node *path_s);
  void eval_edges();
  void erase_path(Node *path_e);
  void insert_path(Node *path_e);
  void renumber_path();
  void inc_edges();		// for evaluation function
  void dec_edges();		// for evaluation function

  Edge *from_edge;		// to previous edge while searching a new path
  Edge *path_to;		// to the next edge in the path
  Edge *path_from;		// from the edge in the path
#if CHECK
  bool been_to;			// path check
#endif
  int sequence_nr;		// for path length
  int nr_of_edges;
  int free_edges;		// number of free edges
  Edge *edges[6];		// edges to other nodes
  int edges_i;			// edge index for search, recursive dumped core
  int floor;
  int row;
  int column;
};

Edge *north;			// for the initial path
Edge *north_south;
Edge *south;
Edge *south_north;
Node *gate = 0;			// entry/exit of path
int gate_row;			// entry row
int rows;			// building dimensions
int columns;
int height;
int caves = 0;			// number of caves
int best_len = 0;
int best_ups = 0;
int full_path_length;
char (*cave)[20][80];		// [floor][row][column]
Node (*cavep)[20][80];		// [floor][row][column]
Node **pending;			// nodes visited during path extension search
int max_pending = 0;
char *best;			// best path found
Node *start_search;		// start room of path extension

// Return a random number r, 0 <= r < upper

inline int
rnd(int upper)
{
  return (rand() >> 1) % upper;
}

// Routines for debugging and testing.
// Skip to compare_edges().

#if DEBUG || CHECK || TEST
// Print a node

ostream &operator<<(ostream &s, Node &node)
{
  s << "floor " << node.floor
    << ", row " << node.row
    << ", column " << node.column;
  if (node.path_to)
    s << " P";
  if (node.from_edge)
    s << " F";
  return s;
}

// Print an edge
 
ostream &operator<<(ostream &s, Edge &edge)
{
  s << edge.dir << ", " << *(edge.from_node) << " -> " << *(edge.to_node);
  return s;
}

// Print path as edges

void
print_path()
{
  cerr << "print path:" << endl;
  Node *path_i = gate; 
  do
  {
    cerr << *(path_i->path_to) << endl;
    path_i = path_i->path_to->to_node;
  } while (path_i != gate);
  cerr << endl;
}

// Print path as directions

void
print_path_dir()
{
  Node *path_i = gate; 
  do
  {
    cerr << path_i->path_to->dir;
    path_i = path_i->path_to->to_node;
  } while (path_i != gate);
  cerr << endl;
}
#endif

#if TEST
// Add from_edges to the path

void
add_from_edges()
{
  Node *path_i(gate);
  Edge *from(0);
  do
  {
    path_i->path_from = from;
    from = path_i->path_to;
    path_i = path_i->path_to->to_node;
  }
  while (path_i != gate);
  path_i->path_from = from;
}

// Return a direction as an integer

int
get_dir(char dir)
{
  char const compass[] = "nesw";
  char *ptr(strchr(compass, dir));
  if (ptr)
    return ptr-compass;
  return -1;
}

// Print the building to look at unused rooms marked with a question mark.
// It uses the graphics characters of the HP2392 terminal to draw the path
// (or was it CIT224+ because the HP broke down.)

void
print_cave()
{
  char const vert('.');
  char const hor(',');
  char const ul('r');
  char const ur('t');
  char const ll('f');
  char const lr('g');
  
  char graph[4][4] =		// n e s w
  {
    { vert, ul, 0, ur },
    { lr, hor, ur, 0 },
    { 0, ll, vert, lr },
    { ll, 0, ul, hor }
  };
  add_from_edges();
  for (int floor = 0; floor < height; floor++)
  {
    fprintf(stderr, "%d\n", floor);
    char const so[] = "\016";	// ^N
    char const si[] = "\017";	// ^O
    bool shift = false;
    for (int row = 1; row < rows-1; row++)
    {
      for (int column = 0; column < columns-1; column++)
      {
	if (cave[floor][row][column] == ' ')
	{
	  Node *node = &cavep[floor][row][column];
	  Edge *edge(node->path_to);
	  if (edge)
	  {
	    int from_nr(get_dir(node->path_from->dir));
	    int to_nr(get_dir(edge->dir));
	    if (from_nr >= 0 && to_nr >= 0 && graph[from_nr][to_nr])
	    {
	      if (!shift)
		cerr << so;
	      shift = true;
	      cerr << graph[from_nr][to_nr];
	    }
	    else
	    {
	      if (shift)
		cerr << si;
	      shift = false;
	      cerr << edge->dir;
	    }
	  }
	  else
	  {
	    if (shift)
	      cerr << si;
	    shift = false;
	    cerr << '?';
	  }
	}
	else
	{
	  if (shift)
	    cerr << si;
	  shift = false;
	  cerr << cave[floor][row][column];
	}
      }
      if (shift)
	cerr << si;
      shift = false;
      cerr << endl;
    }
  }
}

// Print the edges

void
print_edges()
{
  for (int floor = 0; floor < height; floor++)
  {
    fprintf(stderr, "%d\n", floor);
    for (int row = 1; row < rows-1; row++)
    {
      for (int column = 0; column < columns-1; column++)
      {
	if (cave[floor][row][column] == ' ')
	  cerr << cavep[floor][row][column].nr_of_edges;
	else
	  cerr << cave[floor][row][column];
      }
      cerr << endl;
    }
  }
}
#endif

#if CHECK
// Check if the number of free edges in the building haven't gone haywire.

void
check_cave()
{
  for (int floor = 0; floor < height; floor++)
  {
    for (int row = 1; row < rows-1; row++)
    {
      for (int column = 0; column < columns-1; column++)
      {
	Node *node = &cavep[floor][row][column];
	int tally = 0;
	for (int i = 0; i < node->nr_of_edges; i++)
	{
	  if (!node->edges[i]->to_node->path_to) // node not in path?
	    tally++;
	}
	if (tally != node->free_edges)
	{
	  cerr << "free edges = " << node->free_edges << ", tally = "
	    << tally << ", node = " << *node << endl;
	}
      }
    }
  }
}

// Check if the found path through the building is possible.
// This does not protect against input read errors of the building file.

void
check_path()
{
  int ud = 0;
  int ew = 0;
  int ns = gate_row;
  bool at_exit = false;
  Node *path_i = gate; 
  do
  {
    register Edge *edge = path_i->path_to;
    if (at_exit)
      cerr << "Spelunker continued after exit: ns = " << ns
	<< ", ew = " << ew << ", ud = " << ud << endl;
    switch (edge->dir)
    {
    case 'u':
      ud++;
      break;
    case 'd':
      --ud;
      break;
    case 'w':
      --ew;
      break;
    case 'e':
      ew++;
      break;
    case 'n':
      --ns;
      break;
    case 's':
      ns++;
      break;
    default:
      cerr << "illegal direction: " << edge->dir << endl;
    }
    if (ns < 1 || ns > rows ||
	ew < 0 || ew > columns ||
	ud < 0 || ud >= height)
      cerr << "Spelunker out of bounds: ns = " << ns << ", ew = " << ew
	<< ", ud = " << ud << endl;
    if (cave[ud][ns][ew] == '#')
      cerr << "Spelunker ran into a wall: ns = " << ns << ", ew = " << ew
	<< ", ud = " << ud << endl;
    if (cavep[ud][ns][ew].been_to)
      cerr << "Spelunker is running in circles: ns = " << ns << ", ew = " << ew
	<< ", ud = " << ud << endl;
    cavep[ud][ns][ew].been_to = true;
    if (cave[ud][ns][ew] == 'E')
      at_exit = true;
    path_i = path_i->path_to->to_node;
  }
  while (path_i != gate);
  if (!at_exit)
    cerr << "Spelunker did not find exit: ns = " << ns
      << ", ew = " << ew << ", ud = " << ud << endl;

  // clear been_to
  register Node *path_j = gate;
  do
  {
    path_j->been_to = false;
    path_j = path_j->path_to->to_node;
  }
  while (path_j != gate);
}
#endif

// Used for sorting edges

int
compare_edges(void const *p1, void const *p2)
{
  register Edge *e1 = *(Edge **) p1;
  register Edge *e2 = *(Edge **) p2;
  return e1->value - e2->value;
}

// Erase nodes tried for the path extension

void
erase_node_pending()
{
  for (register int nr_pending = 0; nr_pending < max_pending; nr_pending++)
    pending[nr_pending]->from_edge = 0;
}

// Renumber the path nodes

void Node::
renumber_path()
{
  register Node *path_s = this;
  register int seq_nr = path_s->sequence_nr;
  do
  {
    path_s->sequence_nr = seq_nr++;
    path_s = path_s->path_to->to_node;
  }
  while (path_s != gate);
  full_path_length = seq_nr;
}

// Erase path nodes between two rooms

void Node::
erase_path(Node *path_e)
{
#if DEBUG
  if (debug >= 2)
    cerr << "erase_path()" << *this << " " << *path_e << endl;
#endif
  register Node *next_node;
  register Node *path_s = this;
  do
  {
    next_node = path_s->path_to->to_node;
    path_s->path_to = 0;
    path_s->inc_edges();
    path_s = next_node;
  }
  while (path_s != path_e);
#if DEBUG
  if (debug >= 2)
    cerr << "erase_path: " << endl;
#endif
}

// Increment number of free edges for evaluation

void
Node::
inc_edges()
{
  for (register int i = 0; i < nr_of_edges; i++)
    edges[i]->to_node->free_edges++;
}

// Decrement number of free edges for evaluation

void
Node::
dec_edges()
{
  for (register int i = 0; i < nr_of_edges; i++)
    edges[i]->to_node->free_edges--;
}

// Randomize a vector of edges

void
rand_vector(Edge **edges, int nr_of_edges)
{  
  for (register int j = 0; j < nr_of_edges-1; j++)
  {
    register int s = j + rnd(nr_of_edges-j);
    register Edge *t = edges[j];
    edges[j] = edges[s];
    edges[s] = t;
  }
}

// Evaluate the edge, score XY, a lower score is better.
// X = number of free edges of node pointed at by edge.
// Y = minimum number of free edges of adjacent nodes.

void Edge::
eval_edge()
{
  register int val = 7;
  register Node *node = this->to_node;
  for (register int i = 0; i < node->nr_of_edges; i++)
  {
    if (node->edges[i]->to_node->free_edges < val)
      val = node->edges[i]->to_node->free_edges;
  }
  this->value = 8 * node->free_edges + val;
}

// Evaluate the edges of this node

void Node::
eval_edges()
{
  for (register int i = 0; i < nr_of_edges; i++)
    edges[i]->eval_edge();
}

// Search a path extension
// I think that it is a depth first search.

bool
search(Node *path_s, int cut)
{
  Node *node = pending[0];
#if DEBUG2
  cerr << "level " << level << " " << *node << endl;
#endif
  node->dec_edges();
  level = 0;

  for (;;)
  {
    node->eval_edges();
    qsort((void *) node->edges, node->nr_of_edges, sizeof(Edge *),
	  compare_edges);

    // randomize edges with an equal score

    int equal_edges = 0;
    for (register int k = 0; k < node->nr_of_edges; k += equal_edges)
    {
      register int s = node->edges[k]->to_node->free_edges;
      equal_edges = 1;
      for (register int n = k+1; n < node->nr_of_edges; n++)
      {
	if (node->edges[n]->to_node->free_edges == s)
	  equal_edges++;
	else
	  break;
      }      
      rand_vector(&node->edges[k], equal_edges);
    }
    
    node->edges_i = 0;

    // try the sorted and randomized edges

    for (;;)
    {
      Edge *edge;
      if (node->edges_i < node->nr_of_edges)
      {
	edge = node->edges[node->edges_i];
	if (edge->to_node->path_to) // back to path?
	{
#if DEBUG
	  if (debug >= 2)
	    cerr << "path: " << *edge << endl;
#endif
	  int old_len;	// old path length
	  int new_len;
	  register Node *path_e = edge->to_node;
	  edge->to_node->from_edge = edge;
	  // get length of path to be removed
	  if (cut == 1)	// allowed length of path to be removed
	  {
	    if (path_s->path_to->to_node == path_e) // no erase needed?
	      goto shortcut;	// Gasp!
	    else
	      goto skip;	// Aahrgg!
	  }
 
	  old_len = path_s->get_path_length(path_e);
	  if (old_len > 0 && old_len <= cut)
	  {
	    new_len = path_e->pending_path_length(path_s);
	    // get length of new path
	    if (new_len > old_len) // new path longer?
	    {
	    shortcut:
	      for (;;)		// walk path extension
	      {
		node->inc_edges(); // increment free edges of path extension
		level--;
		if (level < 0)
		  break;
		node = node->from_edge->from_node;
	      }
	      path_s->erase_path(path_e);      // remove old path
	      path_s->insert_path(path_e);     // insert path extension
	      if (cut != 1)
		path_s->renumber_path();
	      erase_node_pending();
	      path_s->from_edge = 0;
	      edge->to_node->from_edge = 0;
#if DEBUG2
	      cerr << "search true" << endl;
#endif
	      return true;
	    }
	  }
	skip:
	  edge->to_node->from_edge = 0;
	}
	else if (!edge->to_node->from_edge) // node not pending?
	{
#if DEBUG
	  if (debug >= 2)
	    cerr << "search: " << *edge << endl;
#endif
	  node = edge->to_node;
	  pending[max_pending] = node;
#if DEBUG2
	  cerr << "level++ " << level << " " << *node << endl;
#endif
	  node->dec_edges();	// decrement free edges
	  max_pending++;
	  edge->to_node->from_edge = edge;
	  level++;
	  break;
	}
      }
      else			// tried all edges of node
      {
#if DEBUG2
	cerr << "--level " << level << " " << *node << endl;
#endif
	node->inc_edges();	// increment free edges
	--level;
	if (level < 0)
	{
#if DEBUG2
	  cerr << "search false" << endl;
#endif
	  return false;
	}
	node = node->from_edge->from_node;
      }
      node->edges_i++;
    }
  }
}

// Get the length of the path

int Node::
get_path_length(Node *path_e)
{
  register int end_seq;
  if (path_e == gate)		// gate has sequence number 0
    end_seq = full_path_length;
  else
    end_seq = path_e->sequence_nr;
#if DEBUG
  cerr << "get_path_length() " << end_seq - this->sequence_nr << endl;
#endif
  return end_seq - this->sequence_nr;
}

// Count the number of ups, in case a tie breaker is needed

int
path_ups()
{
  int ups = 0;
  register Node *path_i = gate;
  do
  {
    if (path_i->path_to->dir == 'u')
      ups++;
    path_i = path_i->path_to->to_node;
  }
  while (path_i != gate);
  return ups;
}

// Get the length of the path extension

int Node::
pending_path_length(Node *path_s)
{
#if DEBUG
  if (debug >= 2)
    cerr << "pending_path_length() " << *path_s << " " << *this << endl;
#endif
  register int count = 0;
  for (register Node *node = this; node != path_s;
       node = node->from_edge->from_node)
  {
#if DEBUG
    if (node->from_edge == 0)
      cerr << "error node->from_edge " << *node << endl;
    if (node->from_edge->from_node == 0)
      cerr << "error node->from_edge->from_node " << *(node->from_edge) << endl;
    if (debug >= 2)
      cerr << *(node->from_edge) << endl;
#endif
    count++;
  }
#if DEBUG
  if (debug >= 2)
    cerr << "pending_path_length: " << count << endl;
#endif
  return count;
}

// Insert a path extension in the path

void Node::
insert_path(Node *path_e)
{
#if DEBUG
  if (debug >= 2)
    cerr << "insert_path() " << *this << endl;
#endif
  
  for (register Node *path_i = path_e; path_i != this;
       path_i = path_i->from_edge->from_node)
  {
    path_i->from_edge->from_node->path_to = path_i->from_edge;
    path_i->from_edge->from_node->dec_edges();
  }
}

// Try the first room of a possible path extension.

bool
do_pending(Edge *edge_i, int cut)
{
#if DEBUG
  if (debug >= 2)
    cerr << "do_pending()" << endl;
#endif
    Node *path_s = edge_i->from_node;
    // The current path is stored as pointers to edges.
    path_s->from_edge = path_s->path_to;    // skip this node in search
#if DEBUG
    if (debug >= 2)
    {
      cerr << "search from " << *(path_s->from_edge) << endl;
      cerr << *path_s << endl;
    }
    if (debug >= 1)
      cerr << "try edge " << *edge_i << endl;
#endif
#if DEBUG
      if (debug >= 1)
	cerr << "node ok" << endl;
#endif
      edge_i->to_node->from_edge = edge_i;
	
      pending[0] = edge_i->to_node;
      max_pending = 1;
#if DEBUG
      if (debug >= 1)
	cerr << "pending[0] " << *edge_i << endl;
      if (debug >= 2)
	cerr << "try pending " << *(pending[0]) << endl;
#endif
      level = 0;
      if (search(path_s, cut))	// pending[0] will be used
	return true;
#if DEBUG
      if (debug >= 2)
	cerr << "end of search" << endl;
#endif

      // no extension to path found
      erase_node_pending();
    path_s->from_edge = 0;
#if DEBUG
//  debug = 0;
#endif
  return false;
}

// Walk the path and try to add path extensions

bool
walk_path(int cut)
{
  do
  {
    for (int i = 0; i < start_search->nr_of_edges; i++)
    {
      register Edge *edge_i = start_search->edges[i];
      if (!edge_i->to_node->path_to) // node not in path?
      {
	// the next node in the path must have a free edge to return to
	if (cut > 1 || start_search->path_to->to_node->free_edges >= 1)
	{
	  if (do_pending(edge_i, cut))
	    return true;
	}
      }
    }
    start_search = start_search->path_to->to_node;
  }
  while (start_search != gate && !time_out);
  return false;
}

// Save the longest path

void
save_best()
{
  int ups = -1;
  if (full_path_length > best_len ||
      full_path_length == best_len && (ups = path_ups()) > best_ups)
  {
    if (ups == -1)
      ups = path_ups();
    if (print_score)
      cerr << "path size = " << full_path_length << ", "
	<< "path ups = " << ups << endl;
    best_len = full_path_length;
    best_ups = ups;
    register int i = 0;
    register Node *path_node = gate;
    do
    {
      best[i++] = path_node->path_to->dir;
      path_node = path_node->path_to->to_node;
    }
    while (path_node != gate);
    best[i] = '\0';
  }
}

// Attempt to find different paths until time runs out.

void
do_attempts()
{
#if DEBUG
  if (debug >= 2)
    cerr << "do attempts\n";
#endif

  int gate_count = 0;
  while (!time_out)
  {
    // init path with ns or sn
    gate_count++;
    switch (gate_count)
    {
    case 2:			// path ns
      gate->path_to = north;
      gate->dec_edges();
      north->to_node->path_to = north_south;
      north->to_node->dec_edges();
      break;
    case 1:			// path sn
      gate->path_to = south;
      gate->dec_edges();
      south->to_node->path_to = south_north;
      south->to_node->dec_edges();
      break;
    default:			// start all over again
      gate_count = 0;
      continue;
    }
#if DEBUG
    if (debug >= 2)
      cerr << "start path with: " << endl;
    print_path_dir();
#endif
#if CHECK
    check_cave();
#endif
    start_search = gate;
    
    // Add path extensions without erasing parts of the path

    while (walk_path(1) && !time_out)
    {
#if DEBUG
      if (debug >= 2)
      {
	cerr << "current path: " << endl;
	print_path();
	print_path_dir(); 
      }
#endif
#if CHECK
      check_cave();
      check_path();
#endif
    } // while
#if DEBUG
//    debug = 1;
#endif
#if TEST
//    print_cave();
#endif
    start_search = gate;

    // Add path extensions and allow erasing parts of the path

    gate->renumber_path();
    while (walk_path(16000) && !time_out)
    {
#if CHECK
      check_cave();
      check_path();
#endif
      start_search = gate;
    }
    save_best();
    gate->erase_path(gate);
  }
}

// Time's up

#if __MWERKS__
#else
void
alarm_signal(int)
{
  static struct tms TMS;
  (void) times(&TMS);
    // add the elapsed system and user times
    // calculation comes out to the nearest second - rounded down
  long time_left = max_time - (TMS.tms_stime + TMS.tms_utime)/clk_tck;

  if (time_left > 0)		// still some time left?
  {
    (void) signal(SIGALRM, alarm_signal);
    (void) alarm((unsigned int) time_left);
  }
  else				// time's really up
    time_out = true;
}
#endif

Edge::
Edge(Node *a_from_node, Node *a_to_node, char a_dir)
: from_node(a_from_node), to_node(a_to_node), dir(a_dir)
{
}

Node::
Node()
: from_edge(0), path_to(0)
#if CHECK
  , been_to(false)
#endif
{
}

// Add another edge to the buidling

void Node::
add_edge(char dir, Node *to_node)
{
  edges[nr_of_edges] = new Edge(this, to_node, dir);
//  nr_of_edges++;
  free_edges = ++nr_of_edges;
}

// Find the entrance of the building.
// Get pointers to rooms for the initial path ns and sn.

void
init_entry()
{
#if DEBUG
  if (debug >= 2)
    cerr << "init entry()\n";
#endif
  for (gate_row = 0; gate_row < rows; gate_row++) // find entry/exit
  {
    if (cave[0][gate_row][0] == 'E')
    {
#if DEBUG
//      cerr << "E row = " << gate_row << endl;
#endif
      gate = &cavep[0][gate_row][0];
      gate->sequence_nr = 0;
      north = gate->find_dir('n');
      north_south = north->to_node->find_dir('s');
      south = gate->find_dir('s');
      south_north = south->to_node->find_dir('n');
      break;
    }
  }
}

// Find a direction in an array of edges

Edge *Node::
find_dir(char const a_dir)
{
  for (int i = 0; i < nr_of_edges; i++) // walk edges
  {
    if (edges[i]->dir == a_dir)
      return edges[i];
  }
  return 0;
}

// Convert the 3D building into one with nodes, edges and lots of pointers

void
init_node()
{
#if DEBUG
  if (debug >= 2)
    cerr << "init node\n";
#endif
  for (int floor = 0; floor < height; floor++)
  {
    for (register int row = 0; row < rows; row++)
    {
      for (register int column = 0; column < columns; column++)
      {
	if (cave[floor][row][column] != '#')
	{
	  // add edges
	  register Node *from_node = &cavep[floor][row][column];
	  from_node->floor = floor;
	  from_node->row = row;
	  from_node->column = column;
	  from_node->nr_of_edges = 0;
	  if (floor+1 < height && cave[floor+1][row][column] != '#')
	    from_node->add_edge('u', &cavep[floor+1][row][column]);
	  if (floor-1 >= 0 && cave[floor-1][row][column] != '#')
	    from_node->add_edge('d', &cavep[floor-1][row][column]);
	  if (row+1 < rows && cave[floor][row+1][column] != '#')
	    from_node->add_edge('s', &cavep[floor][row+1][column]);
	  if (row-1 >= 0 && cave[floor][row-1][column] != '#')
	    from_node->add_edge('n', &cavep[floor][row-1][column]);
	  if (column+1 < columns && cave[floor][row][column+1] != '#')
	    from_node->add_edge('e', &cavep[floor][row][column+1]);
	  if (column-1 >= 0 && cave[floor][row][column-1] != '#')
	    from_node->add_edge('w', &cavep[floor][row][column-1]);
	  caves++;		// count free rooms
	}
      }
    }
  }
}

// Read one floor of the building

void
read_floor(ifstream &if_cave, int floor, int rows, int columns)
{
  char buf[100];
  for (register int row = 0; row < rows; row++)
  {
    if_cave.getline(buf, sizeof(buf));
    for (int column = 0; column < columns; column++)
      cave[floor][row][column] = buf[column];      
  }
}

// Read the file with the building and put it in a 3D array

void
read_cave(char const *const filename)
{
#if DEBUG
  if (debug >= 2)
    cerr << "read cave\n";
#endif
  int floor;
  ifstream if_cave(filename);
  if_cave >> floor >> rows >> columns >> height;
  --floor;
  char buf[100];
  if_cave.getline(buf, sizeof(buf));
  
  read_floor(if_cave, floor, rows, columns);
  for (int i = 1; i < height; i++) // read floors
  {
    if_cave >> floor;
    --floor;
    if_cave.getline(buf, sizeof(buf));
    read_floor(if_cave, floor, rows, columns);
  }
}

// Start here...

int
#if __MWERKS__
main()
#else
main(int argc, char *argv[])
#endif
{
  char *in_file;
#if __MWERKS__
  in_file = "test";
#else
  int option;

  while ((option = getopt(argc, argv, "dst:")) != EOF)
  {
    switch (option)
    {
#if DEBUG
    case 'd':
      debug = 10;
      break;
#endif
    case 's':			// print score
      print_score = true;
      break;
    case 't':			// maximum cpu time in seconds, default 600
      max_time = atoi(optarg);
      break;
    default:
      cerr << argv[0] << ": invalid option: " << option << endl;
      exit(1);
    }
  }

  // allocate memory here to prevent executables > 1MB

  best = new char[16000];
  pending = new Node *[16000];
  cave = new char[10][20][80];		// [floor][row][column]
  cavep = new Node[10][20][80];		// [floor][row][column]

  in_file = argv[optind];
  clk_tck = sysconf(_SC_CLK_TCK); // get system clock frequency
  (void) signal(SIGALRM, alarm_signal);
  (void) alarm(max_time);
#endif
  read_cave(in_file);
  init_node();
  init_entry();
  if (print_score)
    cerr << "total caves = " << caves << endl;
#if TEST
//  print_edges();
#endif
  do_attempts();
  cout << best << endl;  // print best solution
  if (print_score)
  {
    cerr << "caves visited = " << best_len << endl;
    cerr << "ups = " << best_ups << endl;
  }
  return 0;
}