cqueen.cpp

解国际象棋的N皇后问题的C++源代码

#include "stdafx.h"
#include "cqueen.h"
Cqueen::Cqueen(int row)
{
	m_bruning=false;
	m_pisaveqplace=NULL;
	m_pgridbitmap=NULL;//栅栏位图
	m_pplacelist=NULL;
	setrow(row);
	m_inowcol=0;
}
Cqueen::Cqueen()
{
	m_bruning=false;
	m_pisaveqplace=NULL;
	m_pplacelist=NULL;
	setrow(0);
}
Cqueen::~Cqueen()
{
	if(m_pisaveqplace!=NULL)
		delete m_pisaveqplace;
	if(m_pgridbitmap!=NULL)
		delete m_pgridbitmap;
	freelist();
}
CSize Cqueen::getqueengridsize()//获取棋盘栅栏的尺寸
{
	return m_sizeview;
}
int Cqueen::getqueenplace(int row)//获取皇后所在的排号
{
	int ret=-1;
	if(row<m_icount&&row>=0)
		ret=m_pisaveqplace[row];//取得保存起来的皇后的位置
	return ret;
}
void Cqueen::setrow(int row)//设置皇后棋盘的排数
{
	if(m_bruning)//？？？
	{
		return;
	}
	m_icount=row;
	m_sizeview.cx=m_icount*40;//1
	m_sizeview.cy=m_icount*40;//2这两个都是用来设置棋盘的大小的
	if(row==0||m_bruning)
		return;
	if(m_pgridbitmap!=NULL)
	{
		delete m_pgridbitmap;
	}
//绘制操作涉及三类对象，一类是输出对象包括CDC及其派生类，一类是绘制工具对象文本图形对象，CFont,CBrush,CPen等,一类是属于基本数据类型，如CPoint,CSize,CRect等
	m_pgridbitmap=new CBitmap();//位图是一种位矩阵，每一个显示象素都对应于其中的一个或多个位。可以利用位图来表示图像，也可以利用它来创建刷子。
	CDC *pDC=CDC::FromHandle(::GetDC(NULL));//返回设备环境类对象的指针
	CDC memdc;
	memdc.CreateCompatibleDC(pDC);
	CRect rect(0,0,m_sizeview.cx,m_sizeview.cy);
	m_pgridbitmap->CreateCompatibleBitmap(pDC,m_sizeview.cx,m_sizeview.cy);
    CBitmap *oldbmp=memdc.SelectObject(m_pgridbitmap);
	//CBrush brush(RGB(255,255,0));//改变棋盘的背景色,刷子定义了一种位图形式的像素，利用它可以对区域内部填充颜色。
	//memdc.FillRect(rect,&brush);
	//CBrush brushblue(RGB(0,255,255));//2改变棋盘的颜色，创建了一个颜色刷子。
	for(int i=0;i<m_icount;i++)//根据棋盘的大小，划出棋盘
	{
		//rect.SetRect(0,0,40,40);//确定棋盘的大小为(左上角坐标，左下角）
		//rect.OffsetRect(0,i*40);//确定移动量（左右，上下）
		for(int j=0;j<m_icount;j++)
		{
			//if(((j+i)%2))
			//	memdc.FillRect(rect,&brushblue);//用2的颜色填充矩形
			//rect.OffsetRect(40,0);
			memdc.FillSolidRect(j*40,i*40,40,40,RGB(68, 71, 140));
			memdc.Draw3dRect(j*40,i*40,40,40,RGB(0,0,225),RGB(225,225,0));
		}
	}
	memdc.SelectObject(oldbmp);
	::ReleaseDC(NULL,pDC->GetSafeHdc());
	if(m_pisaveqplace!=NULL)
		delete m_pisaveqplace;
	m_pisaveqplace=new int [m_icount];
	for(int j=0;j<m_icount;j++)
	{
		m_pisaveqplace[j]=-1;
	}
	freelist();
	m_pplacelist=new placelist[10];
	m_ilistmaxsize=10;
	m_ilistnowsize=0;
	m_idrawindex=-1;
}
void Cqueen::computqueenplace(int column,CView *view)
{
	int row=0;
	int i;
	int col;
	m_inowcol=column;
	if(column==m_icount)
	{
		addplace(m_pisaveqplace);
		m_bruning=false;
		return;
	}
	m_bruning=true;
	int *iplaceover=new int [m_icount];
	for(i=0;i<m_icount;i++)
	{
		iplaceover[i]=true;
	}
	for(i=0;i<column;i++)
	{
		col=m_pisaveqplace[i];
		if((col-(column-i))>=0)
		{
			iplaceover[col-(column-i)]=false;
		}
		if((col+(column-i))<m_icount)
		{
			iplaceover[col+(column-i)]=false;
		}
		iplaceover[col]=false;
	}
	for(i=0;i<m_icount;i++)
	{
		if(iplaceover[i])
		{
			m_pisaveqplace[column]=i;
			if(view!=NULL&&m_idrawindex==-1)
			{
				CDC *pDC=view->GetDC();
				drawqueenn(pDC);
				view->ReleaseDC(pDC);
				Sleep(20);
			}
			computqueenplace(column+1,view);
		}
	}
	m_bruning=false;
	delete[] iplaceover;
	m_inowcol=0;
}
void Cqueen::drawqueenn(CDC *pDC)//画出皇后
{
	CBitmap bitmap;
	CDC memdc;
	memdc.CreateCompatibleDC(pDC);
	bitmap.CreateCompatibleBitmap(pDC,m_sizeview.cx,m_sizeview.cy);
	CBitmap *oldbmp=memdc.SelectObject(&bitmap);
	drawgrid(&memdc);
	drawqueen(&memdc);
	pDC->BitBlt(0,0,m_sizeview.cx,m_sizeview.cy,&memdc,0,0,SRCCOPY);
	memdc.SelectObject(oldbmp);
}
void Cqueen::drawgrid(CDC *pDC)
{
	if(m_pgridbitmap!=NULL)
	{
		CDC memdc;
		memdc.CreateCompatibleDC(pDC);
		CBitmap *oldbitmap=memdc.SelectObject(m_pgridbitmap);
		pDC->BitBlt(0,0,m_sizeview.cx,m_sizeview.cy,&memdc,0,0,SRCCOPY);
		memdc.SelectObject(oldbitmap);
	}
}
void Cqueen::drawqueen(CDC *pDC)//画出棋盘上的皇后
{
	CBrush brush(RGB(255,123,200));//给皇后填充的颜色
	CRect rect;//画皇后的区域大小
	CBrush *oldbrush=pDC->SelectObject(&brush);
	for(int i=0;i<=m_icount;i++)
	{
		rect.SetRect(0,0,40,40);//画皇后的大小
		if(m_idrawindex>-1)//浏览画出的皇后时有用
			rect.OffsetRect(m_pplacelist[m_idrawindex].place[i]*40,i*40);
		else
			rect.OffsetRect(m_pisaveqplace[i]*40,i*40);
		pDC->Rectangle(rect);//确定皇后的形状
	}
	pDC->SelectObject(oldbrush);
}
void Cqueen::addplace(int *place)
{
	if(m_ilistnowsize==m_ilistmaxsize)
	{
		m_ilistmaxsize+=10;
		placelist *temlist=new placelist[m_ilistmaxsize];
		for(int i=0;i<m_ilistnowsize;i++)
		{
			temlist[i].place=m_pplacelist[i].place;
		}
		delete[] m_pplacelist;
		m_pplacelist=temlist;
	}
	int *iplace=new int[m_icount];
	for(int i=0;i<m_icount;i++)
	{
		iplace[i]=place[i];
	}
	m_pplacelist[m_ilistnowsize++].place=iplace;
}
void Cqueen::freelist()
{
	for(int i=0;i<m_ilistnowsize;i++)
	{
		if(m_pplacelist[i].place!=NULL)
		{
			delete[] m_pplacelist[i].place;
		}
	}
	if(m_pplacelist)
	{
		delete[] m_pplacelist;
	}
	m_ilistmaxsize=10;
	m_ilistnowsize=0;
}
void Cqueen::drawlist(int index)
{
	if(index<m_ilistnowsize)
	{
		m_idrawindex=index;
	}
	else
	{
		m_idrawindex=-1;
	}
}
int Cqueen::getlistsize()
{
	return m_ilistnowsize;
}
int Cqueen::getdrawindex()
{
	return m_idrawindex;
}
void Cqueen::savetobmpfile()
{
	CString name;
	CFileDialog fdlg(false,NULL,NULL,OFN_HIDEREADONLY,"bmp file(*.bmp)|*.bmp||");
	if(fdlg.DoModal()==IDOK)
	{
		name=fdlg.GetPathName();
		CString tem;
		tem=name.Right(name.GetLength()-name.ReverseFind('.'));
		tem.MakeLower();
		if(tem!=".bmp")
		{
			name+=".bmp";
		}
	}
	else
	{
		return;
	}
	CDC *pDC=CDC::FromHandle(::GetDC(NULL));
	CBitmap bm;
	bm.CreateCompatibleBitmap(pDC,m_sizeview.cx,m_sizeview.cy);
	CDC tdc;
	tdc.CreateCompatibleDC(pDC);
	CBitmap *pold=tdc.SelectObject(&bm);
	drawqueenn(&tdc);
	tdc.SelectObject(pold);
	BITMAP btm;
	bm.GetBitmap(&btm);
	DWORD size=btm.bmWidthBytes*btm.bmHeight;
	LPSTR lpdata=(LPSTR)::GlobalAlloc(GPTR,size);
	BITMAPINFOHEADER bih;
	bih.biBitCount=btm.bmBitsPixel;
	bih.biClrImportant=0;
	bih.biClrUsed=0;
	bih.biCompression=0;
	bih.biHeight=btm.bmHeight;
	bih.biPlanes=1;
	bih.biSize=sizeof(BITMAPINFOHEADER);
	bih.biSizeImage=size;
	bih.biWidth=btm.bmWidth;
	bih.biXPelsPerMeter=0;
	bih.biYPelsPerMeter=0;
	GetDIBits(pDC->GetSafeHdc(),bm,0,bih.biHeight,lpdata,(BITMAPINFO *)&bih,DIB_RGB_COLORS);
	BITMAPFILEHEADER bfh;
	bfh.bfReserved1=bfh.bfReserved2=0;
	bfh.bfType=((WORD)('M'<<8)|'B');
	bfh.bfSize=54+size;
	bfh.bfOffBits=54;
	CFile bf;
	if(bf.Open(name,CFile::modeCreate|CFile::modeWrite))
	{
		bf.WriteHuge(&bfh,sizeof(BITMAPFILEHEADER));
		bf.WriteHuge(&bfh,sizeof(BITMAPINFOHEADER));
		bf.WriteHuge(lpdata,size);
		bf.Close();
	}
	GlobalFree(lpdata);
	::ReleaseDC(NULL,pDC->GetSafeHdc());
}