mychessboard.cpp

棋盘覆盖问题的算法源程序

// MyChessBoard.cpp: implementation of the CMyChessBoard class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ChessBoard.h"
#include "MyChessBoard.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CMyChessBoard::CMyChessBoard()
{

}

CMyChessBoard::~CMyChessBoard()
{
	delete _p_Mem;
	delete _p_ChessBoard;
}

void CMyChessBoard::Init(void)
{
	
	int i;
	_p_Mem=new unsigned int [_i_BoardHeight*_i_BoardWidth];
	_p_ChessBoard=new unsigned int * [_i_BoardHeight];

	_p_ColorMem=new color [_i_BoardHeight*_i_BoardWidth];
	_p_ColorBoard=new color * [_i_BoardHeight];

	for (i=0;i<_i_BoardHeight;i++)
	{
		_p_ChessBoard[i]=&_p_Mem[i*_i_BoardWidth];
		_p_ColorBoard[i]=&_p_ColorMem[i*_i_BoardWidth];
	}
	//_p_ChessBoard[_i_PlacedX][_i_PlacedY]=0;
	
	memset(_p_Mem,0,_i_BoardHeight*_i_BoardWidth*(sizeof(int)/sizeof(char)));	   //0作为背景
	//for (i=0;i<=_i_BoardHeight-1;i++)
	//{
	//	for (j=0;j<=_i_BoardWidth-1;j++)
	//		TRACE("%d\t",_p_ChessBoard[i][j]);
	//	TRACE("\n");
	//}
	memset(_p_ColorMem,0,_i_BoardHeight*_i_BoardWidth*(sizeof(int)/sizeof(char)));//backColor作为背景
	//for (i=0;i<=_i_BoardHeight-1;i++)
	//{
	//	for (j=0;j<=_i_BoardWidth-1;j++)
	//		TRACE("%d\t",_p_ColorBoard[i][j]);
	//	TRACE("\n");
	//}
	_p_ColorBoard[_i_PlacedX][_i_PlacedY]=white;       //白色作为残局的颜色
	title=1;//从数字1开始标注
	return;
}
/*
 *int tr:棋盘左上角的行号
 *int tc:棋盘左上角的列号
 *int dr:特殊方格的行号
 *int dc:特殊方格的列号
 *int size：棋盘的规格
 */
void CMyChessBoard::FillChessBoard(int tr,int tc,int dr,int dc,int size)
{
	if (size==1) return;

	int		t=title++;
	int		s=size/2;
	/********************************************************/
	//覆盖左上角子棋盘
	if ((dr<tr+s) && (dc<tc+s))
	{   
		//特殊方格在此棋盘中
		FillChessBoard(tr,tc,dr,dc,s);
	}
	else
	{
		//特殊方格不在此棋盘中
		//用t号L型骨牌覆盖右下角
		_p_ChessBoard[tr+s-1][tc+s-1]=t;
		//添颜色

		TRACE("%d\n",t);
		//覆盖其余方格
		FillChessBoard(tr,tc,tr+s-1,tc+s-1,s);
	}

	/********************************************************/
	//覆盖右上角子棋盘
	if ((dr<tr+s) && (dc>=tc+s))
	{   
		//特殊方格在此棋盘中
		FillChessBoard(tr,tc+s,dr,dc,s);
	}
	else
	{
		//特殊方格不在此棋盘中
		//用t号L型骨牌覆盖左下角
		_p_ChessBoard[tr+s-1][tc+s]=t;
		TRACE("%d\n",t);
		//覆盖其余方格
		FillChessBoard(tr,tc+s,tr+s-1,tc+s,s);
	}

	/********************************************************/
	//覆盖左下角子棋盘
	if ((dr>=tr+s) && (dc<tc+s))
	{   
		//特殊方格在此棋盘中
		FillChessBoard(tr+s,tc,dr,dc,s);
	}
	else
	{
		//特殊方格不在此棋盘中
		//用t号L型骨牌覆盖右上角
		_p_ChessBoard[tr+s][tc+s-1]=t;
		TRACE("%d\n",t);
		//覆盖其余方格
		FillChessBoard(tr+s,tc,tr+s,tc+s-1,s);
	}

	/********************************************************/
	//覆盖右下角子棋盘
	if ((dr>=tr+s) && (dc>=tc+s))
	{   
		//特殊方格在此棋盘中
		FillChessBoard(tr+s,tc+s,dr,dc,s);
	}
	else
	{
		//特殊方格不在此棋盘中
		//用t号L型骨牌覆盖左上角
		_p_ChessBoard[tr+s][tc+s]=t;
		TRACE("%d\n",t);
		//覆盖其余方格
		FillChessBoard(tr+s,tc+s,tr+s,tc+s,s);
	}
}
/*
        _______________________________________________
3  		|3  		4  		4  		8  		8  		9 |		9  
3  		|0  		2  		4  		8  		7  		7 |		9  
5  		|2  		2  		6  		10  	10  	7 |		11  
5  		|5  		6  		6  		1  		10  	11|  	11  
13  	|13		 	14  	1  		1  		18  	19|  	19  
13  	|12			14  	14  	18  	18  	17|  	19  
15  	|12			12  	16  	20  	17  	17|  	21  
		|  +---------------------------------------+  |
15  	|15|		16  	16  	20  	20	   |21|   	21  
        ~~~~									   ~~~~
框到的区域是需要着色的范围
 */
void CMyChessBoard::SetColor(int i, int j)
{
	int Counter;
	color ColorID;      //选择的本次添涂使用的颜色
	bool  ColorFlag[6]; //当前对应骨牌周围已经使用过的颜色

	if (_p_ColorBoard[i][j]!=backColor)  return; //如果当前i,j点已经被填色，则返回
	if ((i==_i_PlacedX)&&(j==_i_PlacedY)) return;  //当前是,残局位置
	for (Counter=0;Counter<6;Counter++)  ColorFlag[Counter]=false;
	//测试i,j上面的方格
	Counter=1;
	if (i-1>=0) 
	{
		if (_p_ChessBoard[i-1][j]==_p_ChessBoard[i][j])//如果是需要涂颜色的
		{
			Counter++;
			//检查该方格四周的颜色
			if (i-2>=0) //上方                                 
				ColorFlag[_p_ColorBoard[i-2][j]]=true;
			if (j-1>=0) //左面
				ColorFlag[_p_ColorBoard[i-1][j-1]]=true;
			if (j+1<_i_BoardWidth) //右面
				ColorFlag[_p_ColorBoard[i-1][j+1]]=true;
		}
		else
		{
			ColorFlag[_p_ColorBoard[i-1][j]]=true;
		}
	}
	//检测i,j左面的方格
	if (j-1>=0)
	{
		if (_p_ChessBoard[i][j-1]==_p_ChessBoard[i][j])//如果是需要涂颜色的
		{
			Counter++;
			//检查四周方格
			if (i-1>=0) //上方                                 
				ColorFlag[_p_ColorBoard[i-1][j-1]]=true;
			if (j-2>=0) //左面
				ColorFlag[_p_ColorBoard[i-0][j-2]]=true;
			if (i+1<_i_BoardHeight) //下面
				ColorFlag[_p_ColorBoard[i+1][j-1]]=true;
		}
		else
		{
			ColorFlag[_p_ColorBoard[i][j-1]]=true;
		}
	}
	//检测i,j右面的方格
	if (j+1<_i_BoardWidth)
	{
		if (_p_ChessBoard[i][j+1]==_p_ChessBoard[i][j])//如果是需要涂颜色的
		{
			Counter++;
			//检查四周方格
			if (i-1>=0) //上方                                 
				ColorFlag[_p_ColorBoard[i-1][j+1]]=true;
			if (j+2<_i_BoardWidth) //右面
				ColorFlag[_p_ColorBoard[i-0][j+2]]=true;
			if (i+1<_i_BoardHeight) //下面
				ColorFlag[_p_ColorBoard[i+1][j+1]]=true;
		}
		else
		{
			ColorFlag[_p_ColorBoard[i][j+1]]=true;
		}
	}
	//检测i,j下面的方格
	if (i+1<_i_BoardHeight)
	{
		if (_p_ChessBoard[i+1][j]==_p_ChessBoard[i][j])//如果是需要涂颜色的
		{
			Counter++;
			//检查四周方格
			if (j-1>=0) //左方                                 
				ColorFlag[_p_ColorBoard[i+1][j-1]]=true;
			if (j+1<_i_BoardWidth) //右面
				ColorFlag[_p_ColorBoard[i+1][j+1]]=true;
			if (i+2<_i_BoardHeight) //下面
				ColorFlag[_p_ColorBoard[i+2][j+0]]=true;
		}
		else
		{
			ColorFlag[_p_ColorBoard[i+1][j]]=true;
		}
	}

	if (Counter==3) //如果当前检查的方格中有一个棋盘
	{
		//得到当前合适的颜色
		for (int Count=2;Count<6;Count++)
			if (ColorFlag[Count]==false)	
			{
				ColorID=(color)Count;
				break;
			}
		_p_ColorBoard[i][j]=ColorID;
		if (j-1>=0)					//左面
			if (_p_ChessBoard[i+0][j-1]==_p_ChessBoard[i][j]) _p_ColorBoard[i+0][j-1]=ColorID;
		if (j+1<_i_BoardWidth)		//右面
			if (_p_ChessBoard[i+0][j+1]==_p_ChessBoard[i][j]) _p_ColorBoard[i+0][j+1]=ColorID;
		if (i-1>=0)					//上面
			if (_p_ChessBoard[i-1][j+0]==_p_ChessBoard[i][j]) _p_ColorBoard[i-1][j+0]=ColorID;
		if (i+1<_i_BoardHeight)		//下面
			if (_p_ChessBoard[i+1][j+0]==_p_ChessBoard[i][j]) _p_ColorBoard[i+1][j+0]=ColorID;
	}
}
void CMyChessBoard::FillColour()
{
	//
	int			i,j;
	for (i=0;i<=_i_BoardHeight-1;i++)
	{
		for (j=0;j<=_i_BoardWidth-1;j++)
			if  (_p_ColorBoard[i][j]==backColor)  //如果当前还没有填色
			{
					//if ((i==1)&&(j==5))
					SetColor(i,j);
					//else
					//	SetColor(i,j);
					/*
					#ifdef _DEBUG
					int Col,Row;
					for (Row=0;Row<_i_BoardHeight;Row++)
					{
						for (Col=0;Col<_i_BoardWidth;Col++)
							TRACE("%d\t",_p_ColorBoard[Row][Col]);
						TRACE("\n");
					}
					TRACE("----------------------------------------------\n");
					#endif
					*/
			}
	}
}
void CMyChessBoard::Run()
{
	FillChessBoard(0,0,_i_PlacedX,_i_PlacedY,_i_BoardHeight);
#ifdef _DEBUG
	int i,j;
	for (i=0;i<_i_BoardHeight;i++)
	{
		for (j=0;j<_i_BoardWidth;j++)
			TRACE("%d\t",_p_ChessBoard[i][j]);
		TRACE("\n");
	}
	TRACE("----------------------------------------------\n");
#endif
	FillColour();
#ifdef _DEBUG
	for (i=0;i<_i_BoardHeight;i++)
	{
		for (j=0;j<_i_BoardWidth;j++)
			TRACE("%d\t",_p_ColorBoard[i][j]);
		TRACE("\n");
	}
#endif
	return;
}