checkers.hpp

本程序是主要是扫雷

/*     Copyright(c) Ben Bear 2003-2004  */

//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License as
//  published by the Free Software Foundation; either version 2 of the
//  License, or (at your option) any later version.
//  
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  General Public License for more details.
//  
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
//  02111-1307, USA.

/*  This file definition the chessboard of the Chinese Checkers and
 *  players infomation.
 */

#ifndef __checkers_hpp
#define __checkers_hpp

#include <string>
#include <vector>
#include <algorithm>

#include "info.hpp"
#include "checkers_hole.hpp"

struct player_t
{
  std::string name;
  int start;             // start direction
  int end;               // end dirction
  std::vector<int> chess;// all the chess
};

class checkers
{
public:
  struct setting
  {
    int floor;
    int number;
    bool long_jump;
    int group;
    bool stay_limit;
  };

protected:
  // all holes
  std::vector<int> holes;

  // floor of the checkers
  int floor;
  // number of the holes
  int num_hole;
  // number of one player's chesses
  int num_chess;

  // data of the six players
  player_t player[6];

  // number of players who can play
  int num_player;
  
  // long jump?
  bool long_jump;

  // how many group
  int group;

  // stay limit
  bool stay_limit;

  // set the floor
  void init (const setting& set);

  // search a jump start at hole[h] and direction[d]
  int
  search_jump (int h, int d);
  
  // search all jump of chess[ch], return number of pos
  template <typename iter>
  int search (int p, int ch, iter begin);

  template <typename iter>
  int search_step (int ch, iter begin);

  // player[name] join to direction[d]
  void join (const char* name, int d);

  // player[d] quit this game
  void quit (int d);

  // move chess[hole[s]] to hole[e]
  void move (int s, int e);

  // lay player[p]'s chesses
  void lay_chess (int p);

  // is p1 and p2 in a same group?
  bool is_group(int p1, int p2);

  // test whether player[p] can stay at hole[h]
  bool in_stay(int p, int h);
public:
  checkers ();
  // floor[f] of the checkers, and number[n] of the players
  checkers (const setting& set);
  ~checkers () {}
};

checkers::checkers ()
{
  floor = -1;
  num_player = -1;
  long_jump = false;
  group = 0;
  stay_limit = false;
}

checkers::checkers (const setting& set)
{
  init (set);
}

void
checkers::init (const setting& set)
{
  assert ((set.floor >= 6) && (set.floor % 2 == 0));

  floor = set.floor;
  num_hole = floor * (floor + 1) * 3 + 1;
  num_chess = floor * (floor / 2 + 1) / 4;

  num_player = set.number;

  holes.clear ();
  holes.resize (num_hole, -1);

  long_jump = set.long_jump;
  group = set.group;
  stay_limit = set.stay_limit;
}

/******************  search()  ******************/
template <typename iter> int
checkers::search (int p, int ch, iter begin)
{
  assert (checkers_hole::in(floor, ch));

  checkers_hole h(floor);
  honey_hole h0 = ch;
  int i;
  iter cur = begin;
  iter end = begin;
  *end++ = h0;
  int old_ch = holes[ch];
  holes[ch] = CHESS_NONE;
  while (cur != end)
    {
      for( i = 0; i < 6; ++i )
	{
	  int jump = search_jump (*cur, i);
	  if (jump == CHECKERS_HOLE_ERROR)
	    continue;
	  iter j;
	  for (j = begin; j != end; ++j)
	    if (*j == jump)
	      break;
	  if (j == end)
	    *end++ = jump;
	}
      ++cur;
    }
  for (i = 0; i < 6; i++)
    {
      h = h0;
      h.move (i);
      if (!h.in() || (holes[h] != CHESS_NONE))
	continue;
      iter j;
      for (j = begin; j != end; ++j)
	if (*j == h)
	  break;
      if (j == end)
	*end++ = h;
    }

  if (stay_limit)
    {
      iter j = end;
      while (j != begin)
	if (!in_stay(p, *--j))
	  {
	    --end;
	    for (iter i = j; i < end; ++i)
	      *i = *(i+1);
	  }
    }

  holes[ch] = old_ch;
  return end - begin;
}

template <typename iter> int
checkers::search_step (int ch, iter begin)
{
  assert (checkers_hole::in(floor, ch));

  int n = 0;
  for (int i = 0; i < 6; ++i)
    {
      int h = search_jump (ch, i);
      if (h == CHECKERS_HOLE_ERROR)
	continue;
      
      *begin++ = h;
      ++n;
    }
  return n;
}

/***************  search_jump()  ****************/
int
checkers::search_jump (int h, int d)
{
  assert (checkers_hole::in(floor, h));

  if (long_jump == false)
    {
      checkers_hole mid(floor, h);
      mid.move (d);
      if (!mid.in() || (holes[mid] == CHESS_NONE))
	return CHECKERS_HOLE_ERROR;
      mid.move (d);
      if (!mid.in() || (holes[mid] != CHESS_NONE))
	return CHECKERS_HOLE_ERROR;
      return mid;
    }

  // long jump
  checkers_hole mid(floor, h);
  int dis = 0;
  do
    {
      mid.move (d);
      ++dis;
    }
  while (mid.in() && (holes[mid] == CHESS_NONE));

  if (!mid.in())
    return CHECKERS_HOLE_ERROR;

  for (; dis > 0; --dis)
    {
      mid.move (d);
      if (!mid.in() || ((holes[mid] != CHESS_NONE)
			&& (holes[mid] != CHESS_HELP)))
	return CHECKERS_HOLE_ERROR;
    }
  return mid;
}

void
checkers::join (const char* name, int d)
{
  assert ((name != 0) && (d >= 0) && (d < 6)
	  && (player[d].start != -1) && (player[d].end == -1));

  player[d].name = name;
  player[d].end = (player[d].start + 3) % 6;
}

void
checkers::quit (int d)
{
  assert ((d >= 0) && (d < 6));
  
  player[d].name = "";
  player[d].end = -1;
}

void
checkers::move (int s, int e)
{
  assert (checkers_hole::in(floor, s) && checkers_hole::in(floor, e));
  assert ((holes[s] >= 0) && (holes[s] < 6));

  //  player
  int p = holes[s];
  holes[s] = -1;
  holes[e] = p;

  *std::find (player[p].chess.begin(), player[p].chess.end(), s) = e;
}

void
checkers::lay_chess (int p)
{
  assert ((p >= 0) && (p < 6));
  int dir_x = (p + 1) % 6;
  int dir_y = (p + 2) % 6;
  int chess_floor = floor / 2;
  int ch = 0;
  honey_hole h_x (chess_floor, p, 0);
  for (int i = chess_floor; i > 0; --i)
    {
      h_x.move (dir_x);
      honey_hole h_y (h_x);
      for (int j = i; j > 0; --j)
	{
	  player[p].chess[ch++] = h_y;
	  holes[h_y] = p;
	  h_y.move (dir_y);
	}
    }
}

bool
checkers::is_group (int p1, int p2)
{
  assert ((p1 >= 0) && (p1 < 6) && (p2 >= 0) && (p2 < 6)
	  && (p1 != p2));

  if ((group == 0) || (num_player < 4))
    return false;
  else if (((group == 2) && (num_player == 4))
	   || ((group == 3) && (num_player == 6)))
    {
      if ((p1 + 3 == p2) || (p2 + 3 == p1))
	return true;
      else
	return false;
    }
  else if ((group == 3) && (num_player == 6))
    {
      if (p1 % 2 == p2 % 2)
	return true;
      else
	return false;
    }
}

bool
checkers::in_stay (int p, int h)
{
  assert ((p >= 0) && (p < 6));
  assert (checkers_hole::in(floor, h));

  if (stay_limit == false)
    return true;
  else
    {
      return checkers_hole::inside(floor, h, p);
    }
}

#endif