////////////////////////////////////////////////////////////////////////// // 版权所有// 作者:董波// 日期: 简介:连连看算法//////////////////////////////////////////////////////////////////////////#ifndef _ND_LLKAG_H_ #define _ND_LLKAG_H_#if _MSC_VER > 1000 #pragma once#endif#include // for/* 约定: 0代表空白,其它编号从1开始向后排。。。*/static const int BLANK_GRID = 0;typedef std::vector< POINT2D > PT2D_VEC;class CLLKAg {public:CLLKAg( int iRow = 9, int iCol = 16 );~CLLKAg();public:// 开始游戏,服务器调用void Start( int iCardNum = 20 );// 获得数据信息,用于客户端渲染,也可用于服务器获得初始化信息后下发void GetState( std::vector& vec ) const;// 客户端调用,从网络数据获取状态 void SetState( const int* pStates, unsigned uSize );// 获得内部指针,但是不能修改,只读的const int* GetMap() const;int GetRow() const;int GetCol() const;// 是否是可消除的,是否是可连接的。 bool IsLink( POINT2D ptFirst, POINT2D ptSecond ) const;// 判断是否已经胜利bool IsWin() const;// 清除两个棋子,客户端调用之前通常需要调用IsLinkbool ClearPair( POINT2D ptFirst, POINT2D ptSecond );// 用于调试 #if defined( _DEBUG ) || defined( DEBUG )int* GetMap_D(); // 返回内部指针void RePermutation(); // 重新排列#endif // #if defined( _DEBUG ) || defined( DEBUG )// 内部实现的函数,外部不需要调用。 protected:// 是否是同一直线连通 bool DirectLink( POINT2D ptFirst, POINT2D ptSecond ) const;// 1直角接口连通 bool OneCornerLink( POINT2D ptFirst, POINT2D ptSecond ) const;// 2直角接口连通bool TwoCornerLink( POINT2D ptFirst, POINT2D ptSecond ) const;private:int* m_pMap; // 用于代表地图int m_iRow; // 行数int m_iCol; // 列数};////////////////////////////////////////////////////////////////////////// // 得到地图inline const int* CLLKAg::GetMap() const{return m_pMap;}// 得到行数 inline int CLLKAg::GetRow() const{return m_iRow;}// 得到列数inline int CLLKAg::GetCol() const{return m_iCol;}#if defined( _DEBUG ) || defined( DEBUG ) // 用于调试 inline int* CLLKAg::GetMap_D(){return m_pMap;}#endif // #if defined( _DEBUG ) || defined( DEBUG )#endif // #ifndef _ND_LLKAG_H_////////////////////////////////////////////////////////////////////////// // 版权所有// 作者:董波// 日期: 简介:连连看算法实现//////////////////////////////////////////////////////////////////////////// 使用MFC的时候请解注释下面这行: #include ""#include ""#include #include #include #include /* 一些模板函数*/template < class T >T _max( T lhs, T rhs ){return lhs > rhs ? lhs : rhs;}template < class T > T _min( T lhs, T rhs ){return lhs < rhs ? lhs : rhs;}// 构造,初始化一些内存 CLLKAg::CLLKAg( int iRow /* = 9 */, int iCol /* = 16 */ ):m_iRow(iRow),m_iCol(iCol),m_pMap(NULL){assert( m_iRow * m_iCol >= 2 );m_pMap = new int[ m_iRow*m_iCol ];if( NULL == m_pMap ) { throw std::bad_alloc( "内存分配失败" );}memset( m_pMap, BLANK_GRID, m_iCol * m_iRow );}CLLKAg::~CLLKAg() {if( NULL != m_pMap ){ delete [] m_pMap;}}// 服务器调用,这将随机生成一个棋盘(地图、桌面) void CLLKAg::Start( int iCardNum /* = 20 */){assert( ( m_iCol * m_iRow % 2 == 0 ) && "必须为偶数" );// 根据系统时间初始化种子 srand( static_cast( time(NULL) ) );// 初始化的基本思想: // 成对的随机填充,然后随机打乱。int iSize = m_iCol * m_iRow;int i = 0;while ( i< iSize ){ int iTarget = rand() % iCardNum + 1; m_pMap[i] = iTarget; ++i; m_pMap[i] = iTarget; ++i;}std::random_shuffle( m_pMap, m_pMap + iSize ); }// 客户端调用,使用网络传递来的信息来初始化游戏状态 void CLLKAg::SetState( const int* pStates, unsigned uSize ){assert( uSize == m_iRow * m_iCol * sizeof (int) );memcpy( m_pMap, pStates, uSize ); }// 得到地图状态 void CLLKAg::GetState( std::vector& vec ) const{( m_pMap, m_pMap + m_iRow*m_iCol );}// 判断是否已经获胜 bool CLLKAg::IsWin() const{const int iSize = m_iCol * m_iRow;for( int i=0; i< iSize; ++i ){ if( BLANK_GRID != m_pMap[i] ) { return false; }}return true; }// 是否是直接连通! bool CLLKAg::DirectLink( POINT2D ptFirst, POINT2D ptSecond )const{// 根本不可能在一条直线上的时候直接返回falseif( ( != ) && ( != ) ){ return false;}// 不应该是相同的点,这是不能接受的! if( ( == ) && ( == ) ){ return false;}// 分情况// 同一x if( == ){ int iMin = _min( , ); int iMax = _max( , ); for( int i=iMin +1; i< iMax; ++i ) { if( m_pMap[i*m_iCol + ] != BLANK_GRID ) { return false; } } return true; }else{ int iMin = _min( , ); int iMax = _max( , ); for( int i=iMin+1; i=0; --i ){ if( m_pMap[*m_iCol +i] != BLANK_GRID ) { break; } POINT2D ptOne = { i, }; if( OneCornerLink( ptOne, ptSecond ) ) { return true; }}// 再向右 for( i=; i=0; --i ){ if( m_pMap[i*m_iCol+] != BLANK_GRID ) { break; } POINT2D ptOne = { , i }; if( OneCornerLink( ptOne, ptSecond ) ) { return true; }}// 向下 for( i=; i