cube.cpp

这个游戏的算法不错

// Cube.cpp: implementation of the CCube class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MxCubes.h"
#include "Cube.h"

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


///////////////////////////////////////
const int CDirc::UP    = 0x00000001;
const int CDirc::DOWN  = 0x00000010;
const int CDirc::LEFT  = 0x00000100;
const int CDirc::RIGHT = 0x00001000;
const int CDirc::FRONT = 0x00010000;
const int CDirc::BACK  = 0x00100000;
///////////////////////////////////////


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

void CCube::InitCube()
{
	int n, k;
	for(n=0; n<6; n++)
	{
		for(k=0; k<9; k++)
		{
			m_Plane[n].block[k].color = COLOR[n];
			m_Plane[n].block[k].dirc.value  = CDirc::UP;
		}
	}
	m_nStep = 20;
}

CCube::CCube()
{
	COLOR[0] = RGB(255,0,0);
	COLOR[1] = RGB(0,255,0);
	COLOR[2] = RGB(0,0,255);
	COLOR[3] = RGB(255,255,0);
	COLOR[4] = RGB(0,255,255);
	COLOR[5] = RGB(255,0,255);
	InitCube();
}

CCube::~CCube()
{

}

void CCube::ShowCube(CDC *pDC, POINT Vertex0, int SideLength)
{
	// length unit by pixel
	double kkk = 0.7071067812;
	kkk = kkk*kkk;
	CPoint V = Vertex0;
	int blocksl; // block side length
	blocksl = SideLength/3;
	int blockslot; 
	blockslot = blocksl/10;
	if(blockslot<1) blockslot = 1;
	else if(blockslot>10) blockslot = 10;
	CPoint rgnp[4];
	int x,y,t;
	// front plane
	t = blocksl+blockslot-1;
	for(x=0; x<3; x++)
	for(y=0; y<3; y++)
	{
		pDC->FillRect(&CRect(CPoint(V.x+x*t,V.y+y*t),CSize(blocksl-1,blocksl-1)), \
			&CBrush(m_Plane[4].block[x*3+y].color));
	}
	for(y=0; y<3; y++)
	{
		rgnp[0] = CPoint(V.x,V.y+y*t);
		rgnp[1] = CPoint(V.x,rgnp[0].y+blocksl);
		rgnp[2] = CPoint(V.x+3*t,rgnp[1].y);
		rgnp[3] = CPoint(rgnp[2].x,rgnp[0].y);
		m_xClickOgram[y].Open(rgnp);
	}
	// right plane
	V.x = Vertex0.x+3*(blocksl+blockslot-1)+blockslot/2;
	V.y = Vertex0.y-int(blockslot*kkk); 
	t = (blocksl+blockslot-1);
	for(x=0; x<3; x++)
	for(y=0; y<3; y++)
	{
		rgnp[0] = CPoint(V.x+int(x*t*kkk),V.y+y*t-int(x*t*kkk));
		rgnp[1] = rgnp[0]+CSize(0, blocksl-1);
		int tt;
		tt = int((blocksl-1)*kkk);
		rgnp[2] = CPoint(rgnp[0].x+tt,rgnp[1].y-tt);
		rgnp[3] = rgnp[2]+CSize(0, 1-blocksl);
		CRgn rgn;
		rgn.CreatePolygonRgn(rgnp,4,ALTERNATE);
		pDC->FillRgn(&rgn,&CBrush(m_Plane[3].block[x*3+y].color));
	}
	for(x=0; x<3; x++)
	{
		rgnp[0] = V      +CSize(int(x*t*kkk),int(0.05*t)-int(x*blocksl*kkk));
		rgnp[1] = rgnp[0]+CSize(0,int(2.8*t));
		rgnp[2] = rgnp[1]+CSize(int(blocksl*kkk), -int(blocksl*kkk));
		rgnp[3] = rgnp[0]+rgnp[2]-rgnp[1];
		m_xClickOgram[3+x].Open(rgnp);
	}
	// up plane
	V.x = Vertex0.x; 
	V.y = Vertex0.y-blockslot;
	V.y = V.y-int((3*blocksl+2*blockslot-1)*kkk);
	V.x = V.x+int((3*blocksl+2*blockslot-1)*kkk);
	t = (blocksl+blockslot-1);
	for(x=0; x<3; x++)
	for(y=0; y<3; y++)
	{
		int tt,ttt;
		rgnp[0] = CPoint(V.x+x*t-int(y*t*kkk),V.y+int(y*t*kkk));
		ttt = int((blocksl-1)*kkk);
		rgnp[1] = rgnp[0]+CSize(-ttt,ttt);
		tt = int((blocksl-1)*kkk);
		rgnp[2] = CPoint(rgnp[1].x+(blocksl-1),rgnp[1].y);
		rgnp[3] = rgnp[2]+CSize(ttt,-ttt);
		CRgn rgn;
		rgn.CreatePolygonRgn(rgnp,4,ALTERNATE);
		pDC->FillRgn(&rgn,&CBrush(m_Plane[0].block[x*3+y].color));
	}
	for(x=0; x<3; x++)
	{
		rgnp[0] = V      +CSize(int(x*t),0);
		rgnp[1] = rgnp[0]+CSize(-int(3*t*kkk),int(3*t*kkk));
		rgnp[2] = rgnp[1]+CSize(int(blocksl), 0);
		rgnp[3] = rgnp[0]+rgnp[2]-rgnp[1];
		m_xClickOgram[6+x].Open(rgnp);
	}
}

void CCube::RgnClicked(int nRgn)
{
	NextPlane(m_Plane, nRgn);
}

void CParallelogram::Open(CPoint *pv)
{
	xLB = pv[1];
	for(int n=0; n<4; n++)
	{
		vt[n] = pv[n]-xLB;
	}
}

BOOL CParallelogram::PtInOgram(CPoint pt)
{
	pt = pt-xLB;
	if(pt.x<0 || pt.x>vt[3].x || pt.y>0 || pt.y<vt[3].y) return FALSE;
	int type = 0;
	if(vt[0].x == vt[1].x && vt[0].y == vt[3].y) type = 0;
	else if(vt[0].x == vt[1].x) type = 1;
	else type = 2;
	switch(type)
	{
	case 0:
		return TRUE;
	case 1:
		if(pt.y>-pt.x+vt[0].y && pt.y<-pt.x) return TRUE;
		break;
	case 2:
		if(pt.x>-pt.y && pt.x<-pt.y+vt[2].x) return TRUE;
		break;
	}
	return FALSE;
}

int CCube::Rotate(int n)
{
	int y = -1;
	if(n<0 || n>8) return -1;
	switch(n)
	{
	case 0:
		y = 6;
		break;
	case 1:
		y = 3;
		break;
	case 2:
		y = 0;
		break;
	case 3:
		y = 7;
		break;
	case 4:
		y = 4;
		break;
	case 5:
		y = 1;
		break;
	case 6:
		y = 8;
		break;
	case 7:
		y = 5;
		break;
	case 8:
		y = 2;
		break;
	}
	return y;
}

int CCube::Rot(int n, int time)
{
	if(time<0) return -1;
	time = time%4;
	while(time--)
	{
		n = Rotate(n);
	}
	return n;
}

void CCube::Turnto(int nDirc)
{
//	if(nDirc<0 || nDirc>3) return;
	int n,k;
	// 0~3: left right up down	switch(nDirc)
	switch(nDirc)
	{
	case 0:
		for(n=0; n<3; n++)
		{
			for(k=0; k<3; k++)
			{
				RgnClicked(n);
			}
		}
		break;
	case 1:
		for(n=0; n<3; n++)
		{
			RgnClicked(n);
		}
		break;
	case 2:
		for(n=6; n<9; n++)
		{
			for(k=0; k<3; k++)
			{
				RgnClicked(n);
			}
		}
		break;
	case 3:
		for(n=6; n<9; n++)
		{
			RgnClicked(n);
		}
		break;
	}
}

void CCube::Randomize(int nStep)
{
	CTime now;
	if(nStep<1 || nStep>100) return;
//	m_nStep = nStep;
	InitCube();
	now = CTime::GetCurrentTime();
	int n = now.GetYear()*10000+now.GetDay()*100+now.GetSecond();
	int t,m,k;
	srand(n);
	int STEP;
	STEP = rand();
	if(STEP<0) STEP = -STEP;
	STEP = STEP%nStep+1;
	for(n=0; n<STEP; n++)
	{
		t = rand();
		if(t<0) t = -t;
		t = t%4;
		m = rand();
		if(m<0) m = -m;
		m = m%9;
		for(k=0; k<3/*t*/; k++)
		{
			RgnClicked(m);
		}
	}
	char msg[100];
	sprintf(msg, "实际打乱的步长是%d", STEP);
	m_nStep = STEP;
	AfxMessageBox(msg);
}

BOOL CCube::IsOK()
{
	return IsOK(m_Plane);
}

BOOL CCube::Restore(int* pnPath, int& nStepCnt)
{
	nStepCnt = 0;
	return Find(m_Plane,pnPath,nStepCnt);
}

BOOL CCube::Find(CPlane *plane, int *pnPath, int& nStepCnt)
{
	CPlane tp[6];
	if(nStepCnt>=m_nStep) return FALSE;
	int n,k;
	for(n=0; n<9; n++)
	{
		for(k=0; k<6; k++)
		{
			tp[k] = plane[k];
		}
		NextPlane(tp, n);
		pnPath[nStepCnt++] = n;
		if(IsOK(tp)) return TRUE;
		if(Find(tp, pnPath, nStepCnt)) return TRUE;
		nStepCnt--;
	}
	return FALSE;
}

void CCube::NextPlane(CPlane *plane, int nRgn)
{
	CBlock xt;
	int n;
	switch(nRgn)
	{
	case 0:
	case 1:
	case 2: // 4 2 5 3
		nRgn = nRgn%3;
		for(n=nRgn; n<9; n+=3)
		{
			xt = plane[4].block[n];
			plane[4].block[n] = plane[2].block[n];
			plane[2].block[n] = plane[5].block[n];
			plane[5].block[n] = plane[3].block[n];
			plane[3].block[n] = xt;
		}
		break;
	case 3:
	case 4:
	case 5: // 3 0 2 1
		nRgn = nRgn%3;
		for(n=3*nRgn; n<3*nRgn+3; n+=1)
		{
			xt = plane[3].block[n];
			plane[3].block[n] = plane[0].block[Rot(n,3)];
			plane[0].block[Rot(n,3)] = plane[2].block[Rot(n,2)];
			plane[2].block[Rot(n,2)] = plane[1].block[Rot(n,1)];
			plane[1].block[Rot(n,1)] = xt;
		}
		break;
	case 6:
	case 7:
	case 8: // 0 5 1 4
		nRgn = nRgn%3;
		for(n=3*nRgn; n<3*nRgn+3; n+=1)
		{
			xt = plane[0].block[n];
			plane[0].block[n] = plane[5].block[Rot(n,2)];
			plane[5].block[Rot(n,2)] = plane[1].block[Rot(n,2)];
			plane[1].block[Rot(n,2)] = plane[4].block[Rot(n,0)];
			plane[4].block[Rot(n,0)] = xt;
		}
		break;
	default:
		return;
	}
}

BOOL CCube::IsOK(CPlane *plane)
{
	int n, k;
	COLORREF cl;
	for(n=0; n<6; n++)
	{
		cl = plane[n].block[0].color;
		for(k=1; k<9; k++)
		{
			if(plane[n].block[k].color != cl)
				return FALSE;
//			plane[n].block[k].dirc.value  = CDirc::UP;
		}
	}
	return TRUE;
}