dlgpaintqipan.cpp

算法分析里的棋盘覆盖问题

// DlgPaintQipan.cpp : implementation file
//

#include "stdafx.h"
#include "CoverProblem.h"
#include "DlgPaintQipan.h"

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

/////////////////////////////////////////////////////////////////////////////
// CDlgPaintQipan dialog


CDlgPaintQipan::CDlgPaintQipan(CWnd* pParent /*=NULL*/)
	: CDialog(CDlgPaintQipan::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDlgPaintQipan)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void CDlgPaintQipan::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDlgPaintQipan)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CDlgPaintQipan, CDialog)
	//{{AFX_MSG_MAP(CDlgPaintQipan)
	ON_WM_PAINT()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDlgPaintQipan message handlers

void CDlgPaintQipan::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	CPen pen;
	pen.CreatePen(PS_SOLID,1,RGB(255,0,0));
	dc.SelectObject(&pen);
	
	CRect rc;  
	this->GetClientRect(&rc);
	int x = rc.CenterPoint().x;
	int y = rc.CenterPoint().y;

	//画棋盘边缘框架
	dc.Rectangle(x-pow(2,m_size-1)*m_length,y-pow(2,m_size-1)*m_length,x+pow(2,m_size-1)*m_length,y+pow(2,m_size-1)*m_length);

	x = x-(pow(2,m_size-1)-1)*m_length; //第一条纵横线的交叉点
	y = y-(pow(2,m_size-1)-1)*m_length;
	
	//画棋盘线
	for (int i=1; i<=pow(2,m_size)-1;i++)
	{
		dc.MoveTo(x-m_length*i,y);
		dc.LineTo(x+m_length*(pow(2,m_size)-i),y);
		dc.MoveTo(x,y-m_length*i);
		dc.LineTo(x,y+m_length*(pow(2,m_size)-i));
		
		x = x + m_length;
		y = y + m_length;
	}
	
	//随机产生残缺块的位置
	int row;   //行位置，y相关
	int col;   //列位置，x相关
	row = rand()%(int)(pow(2,m_size));
	col = rand()%(int)(pow(2,m_size));

	//棋盘左角顶点坐标
	int qiX = rc.CenterPoint().x - (pow(2,m_size-1))*m_length + col*m_length;
	int qiY = rc.CenterPoint().y - (pow(2,m_size-1))*m_length + row*m_length;



  
    //覆盖
	cover(0,0,row,col,pow(2,m_size));
	m_qipan[row][col] = 0;
	for (i=0;i<pow(2,m_size);i++)
		for (int j=0;j<pow(2,m_size);j++)
		{
			PaintOne(dc,rc,i,j,m_flag[m_qipan[i][j]],m_qipan[i][j]);
		}

	CBrush   NewBrush;  
    NewBrush.CreateSolidBrush(RGB(255,0,0));     //初始化画刷 
	dc.SelectObject(&NewBrush);
    dc.Rectangle(qiX+1,qiY+1,qiX+m_length-1,qiY+m_length-1); 

	for (i=0;i<4;i++)
	{
		CString s;
		s.Format("需要%d号三格板的数目是：%d",i+1,m_num[i]);
		dc.TextOut(10,10+20*i,s);
	}
	// Do not call CDialog::OnPaint() for painting messages
	
}


BOOL CDlgPaintQipan::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	m_sum = 0;
	for (int i=0;i<4;i++)
	{
		m_num[i] = 0;
	}

	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}


void CDlgPaintQipan::SetSize(int size, int length)
{
	m_size = size;
	m_length = length;
}

int CDlgPaintQipan::cover(int tr, int tc, int dr, int dc, int size)
{
	int s,t;
	if(size<2)
		return 0;
	m_sum = m_sum+1;
	t = m_sum;         //所使用三格板的数目
	s = size/2;
	if (dr<tr+s && dc<tc+s)         //残缺方格位于左上棋盘
	{
		cover(tr,tc,dr,dc,s);
		m_num[0]++;
		m_flag[t] = 1;
		m_qipan[tr+s-1][tc+s] = t;   //覆盖1号三格板
		m_qipan[tr+s][tc+s-1] = t;
		m_qipan[tr+s][tc+s] = t;
		cover(tr,tc+s,tr+s-1,tc+s,s);
		cover(tr+s,tc,tr+s,tc+s-1,s);
		cover(tr+s,tc+s,tr+s,tc+s,s);
	}
	else if(dr<tr+s && dc>=tc+s)    //残缺方格位于右上棋盘
	{
		cover(tr,tc+s,dr,dc,s);
		m_num[1]++;
		m_flag[t] = 2;
		m_qipan[tr+s-1][tc+s-1] = t;   //覆盖2号三格板
		m_qipan[tr+s][tc+s-1] = t;
		m_qipan[tr+s][tc+s] = t;
		cover(tr,tc,tr+s-1,tc+s-1,s);
		cover(tr+s,tc,tr+s,tc+s-1,s);
		cover(tr+s,tc+s,tr+s,tc+s,s);
	}
	else if (dr>=tr+s && dc<tc+s)        //残缺方格位于左下棋盘
	{
		cover(tr+s,tc,dr,dc,s);
		m_num[2]++;
		m_flag[t] = 3;
		m_qipan[tr+s-1][tc+s-1] = t;   //覆盖3号三格板
		m_qipan[tr+s-1][tc+s] = t;
		m_qipan[tr+s][tc+s] = t;
		cover(tr,tc,tr+s-1,tc+s-1,s);
		cover(tr,tc+s,tr+s-1,tc+s,s);
		cover(tr+s,tc+s,tr+s,tc+s,s);
	}
	else if (dr>=tr+s &&dc>=tc+s)         //残缺方格位于右下棋盘
	{
		cover(tr+s,tc+s,dr,dc,s);
		m_num[3]++;
		m_flag[t] = 4;
		m_qipan[tr+s-1][tc+s-1] = t;   //覆盖4号三格板
		m_qipan[tr+s-1][tc+s] = t;
		m_qipan[tr+s][tc+s-1] = t;
		cover(tr,tc,tr+s-1,tc+s-1,s);
		cover(tr,tc+s,tr+s-1,tc+s,s);
		cover(tr+s,tc,tr+s,tc+s-1,s);
	}

}



void CDlgPaintQipan::PaintOne(CPaintDC &dc,CRect &rc,int row,int col,int flag,int num)  //绘制指定行号，列号的单元格
{

	int qiX = rc.CenterPoint().x - (pow(2,m_size-1))*m_length + col*m_length;
	int qiY = rc.CenterPoint().y - (pow(2,m_size-1))*m_length + row*m_length;

	COLORREF color;
	switch(flag)
	{
	case 1:
		color = RGB(0,0,0);
		break;
	case 2:
		color = RGB(0,255,0);
		break;
	case 3:
		color = RGB(0,0,255);
		break;
	case 4:
		color = RGB(125,125,125);
		break;
	default: ;
	}
	CBrush   NewBrush;  
    NewBrush.CreateSolidBrush(color);     //初始化画刷     
	dc.SelectObject(&NewBrush);
    dc.Rectangle(qiX+1,qiY+1,qiX+m_length-1,qiY+m_length-1); 
	CString s;
	s.Format("%d",num);
	dc.TextOut(qiX+m_length/2-4,qiY+m_length/2-4,s);
}