拼图view.cpp

this code show how to use computer sole the poblem to piece image together

// 拼图View.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "拼图.h"

#include "拼图Doc.h"
#include "拼图View.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMyView

IMPLEMENT_DYNCREATE(CMyView, CView)

BEGIN_MESSAGE_MAP(CMyView, CView)
	//{{AFX_MSG_MAP(CMyView)
	ON_WM_KEYDOWN()
	ON_WM_RBUTTONUP()
	ON_WM_LBUTTONUP()
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONDBLCLK()
	ON_WM_CANCELMODE()
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction
//程序名称：拼图解法
//程序功能：解出拼图的所有方法
//开发人员：钟宇料
//开始日期：2006/6/23
//完成日期：2006/6/26
//版本信息：1.0
//最后修改时间：
//符加注释：

struct Block
{
	CPoint e[4][5];//这里增加了各个方向的存储
		int t;
		int x;
		int y;
 } k[12];


//存储每个模块的颜色，包括空格时
COLORREF color[13]={
					RGB(200,250,176),RGB(242,149,253),RGB(252,150,201),
					RGB(199,148,254),RGB(90,  78,248),RGB(74,193, 251),
					RGB(103,232,253),RGB(190,228,203),RGB(213,207, 98),
					RGB(197,114,114),RGB(234,104, 77),RGB(255, 29, 11),
					RGB( 46,240, 20)
					};

//存储所有模块
static Ary[6][10] = {
	{1,1,1,2 ,2,3, 4, 4, 5, 5},
	{6,6,1,2 ,3,3, 3, 4, 4, 5},
	{9,6,1,2 ,2,3, 8, 8, 4, 5},
	{9,6,6,7 ,7,7,11, 8, 8, 5},
	{9,9,7,7,11,11,11,8,12,12},
	{9,10,10,10,10,10,11,12,12,12}};

int num = 0 ;//记录解法

int A[6][10];//表示二维平面
double t1, t2;
int show = 0;

CMyView::CMyView()
{
	int i=0,j=0,u=0,f=0,tep;
//////////////////////////////////////////
//第1个方向的模块存储
    for( i=0;i<12;i++)
	{
		k[i].t = 0;//t记录检测到每个模块的第几个格子
	}
    for( i =0;i<6;i++)			//从左到右检测
	{
		for( j=0;j<10;j++)		//从上到下检测
		{   
			u=Ary[i][j]-1;
            tep = k[u].t;
			k[u].e[0][tep].x = j;//先检测到的放在前面
            k[u].e[0][tep].y = i;//
            k[u].t++;
		}
	}
//////////////////////////////////////////
//第2个方向的模块存储
    
	for( i=0;i<12;i++)
	{
	   k[i].t=0;
	}

    for( j=9;j>=0;j--)       //后从右到左检测
	{
		for( i =0;i<6;i++)   //先从上到下检测
		{   
			u=Ary[i][j]-1;
            tep = k[u].t;
			k[u].e[1][tep].x = i;
            k[u].e[1][tep].y = 9-j;
            k[u].t++;
		}
	}
//////////////////////////////////////////
//第3个方向的模块存储
	for( i=0;i<12;i++)
	{
	   k[i].t=0;
	}

    for( i=5;i>=0;i--)
	{
		for( j=9;j>=0;j--)
		{   
			u=Ary[i][j]-1;
            tep = k[u].t;
			k[u].e[2][tep].x = 9-j;
            k[u].e[2][tep].y = 5-i;//为什么这样的？？？？？？？？？？？？？？？？？
            k[u].t++;
		}
	}

////////////////////////////////////////////
//第4个方向的模块存储
	for( i=0;i<12;i++)
	{
	   k[i].t=0;
	}

	for( j=0;j<=9;j++)
	{
		for( i =5;i>=0;i--)
		{   
			u=Ary[i][j]-1;
            tep = k[u].t;
			k[u].e[3][tep].x = 5-i;
            k[u].e[3][tep].y = j;
            k[u].t++;
		}
	}

//最后对搜索到的模块进行统一整理，
//整理成结构体存储的第一个模块的格子是第一行第一个
	for( i =0;i<12;i++)
	{
	    for( f=0;f<4;f++)
		{
			for( j=4;j>=0;j--)
			{   			
				k[i].e[f][j].x = k[i].e[f][j].x - k[i].e[f][0].x;
			    k[i].e[f][j].y = k[i].e[f][j].y - k[i].e[f][0].y;
			}
			k[i].t = 0;
		}
	}

//初始化二维平面为空平面
	for( i =0;i<6;i++)
	{
		for( j=0;j<10;j++)
		{ 
			A[i][j]=0;
		}
	}
	
}

CMyView::~CMyView()
{
}

BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMyView drawing

void CMyView::OnDraw(CDC* pDC)
{

	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	CPen penblack;								//创建画笔
	CBrush brush;								//创建画刷

    penblack.CreatePen(PS_SOLID,2,RGB(100,30,0));
	pDC->SelectObject(&penblack);               //画笔线条颜色	
	

   int t_X,t_Y,i,j;

	/*for(int f =0;f<4;f++)
	for( i=0;i<12;i++)
	{ 
		for( j=0;j<5;j++)
		{
			brush.CreateSolidBrush(color[i]);
			pDC->SelectObject(&brush);                  //画刷颜色

			t_X =30+ 10*(k[i].e[f][j].x)+60*i;
			t_Y =20+ f*50 +10*(k[i].e[f][j].y);
			pDC->Rectangle(t_X,t_Y,t_X+10,t_Y+10);
	        brush.DeleteObject();
		}
		pDC->MoveTo(0,40*i+f*50-120);
		pDC->LineTo(900,40*i+f*50-120);
	}

    brush.DeleteObject();*/
	brush.CreateSolidBrush(color[0]);
	pDC->SelectObject(&brush);                  //画刷颜色


    //画出二维平面
	for( i=0;i<6;i++)
	{ 
		for( j=0;j<10;j++)
		{
			t_X = 30*j;
			t_Y = 30*i;
			pDC->Rectangle(t_X,t_Y,t_X+30,t_Y+30);
		}
	}

	pDC->TextOut(2,180,"按任意键开始！！");
	pDC->TextOut(2,220,"拼图解法个数：    个");
	pDC->TextOut(330,210,"请等待.......");

    brush.DeleteObject();
	penblack.DeleteObject();
}

//检测哪些模块可以放入该位置
int CMyView::Check_K(int p_k[],int p_k_f[12][5],int x,int y)
{
    int tX,tY,d=0,l=0,ll = 4;
	for(int i=0;i<12;i++)
	{
		if(k[i].t!=1)					//此模块没有被装填过
		{   
		    if(i == 5 || i == 9)
			  ll = 2;
			else if(i == 2)
			  ll =1;
			  else ll=4;

			for(int f=0;f<ll;f++)
			{
				for(int j=0;j<5;j++)
				{
					tX = k[i].e[f][j].x+x;  
					tY = k[i].e[f][j].y+y;   
					if(A[tY][tX]!=0||
					!(tX>-1 && tX<10 && tY>-1 && tY<6))
						//检测模块的每个位置是否合适
						//不合适的将跳出循环
						break;
			   	}
				if(j==5)
				{
				//记录该位置可以放置的模块的状态
					p_k_f[d][l]=f;	
					l++;
				}
			}
             p_k_f[d][l] = -1;//结尾标记
    	}
		if(l!=0)
		{
			p_k[d] = i;
			d++;
			l=0;
		}
	}
    p_k[d] = -1;//结尾标记
    return 1;
}


void CMyView::put_k_A(int u,int v,int x,int y)
{  
	int tX,tY;
	for(int j=0;j<5;j++)
	{								
		tX = k[u].e[v][j].x;
		tY = k[u].e[v][j].y;
		A[y+tY][x+tX] = u+1;	//在该区域中写上对应模块的号码
	}

    k[u].t = 1;					//标记模块不可用
	k[u].x = x;					//记录模块的起点位置
	k[u].y = y;
	
	if(show == 1)
	{
		s();
		Sleep(100);
	}
}

void CMyView::Next(int &x,int &y)
{
    do{
		if(x<9)
		{
			x++;
		}
		else 
		{
			x=0;
			y++;
		}
	}
	while(A[y][x] != 0);
}
//清空该位置所填的模块，并更改成这个模块使用的位置坐标
void CMyView::Resume(int u,int v,int &x,int &y)
{
	int tX,tY;
	x = k[u].x ;
    y = k[u].y ; 

	for(int j=0;j<5;j++)
	{	
		tX = k[u].e[v][j].x;
		tY = k[u].e[v][j].y;
		A[y+tY][x+tX] = 0;
	}
	k[u].t = 0;
	if(show == 1)
	{
		s();
		Sleep(100);
	}
}

//将符合解的拼图绘画出来
void CMyView::s()
{
	CClientDC dc(this);
	CPen pen;
	CBrush brush;
	char c[10];
	for(int i=0;i<6;i++)
	{
		for(int j=0;j<10;j++)
		{
   			brush.CreateSolidBrush(color[A[i][j]]);
			dc.SelectObject(&brush);               //画刷颜色
			dc.Rectangle(j*30,i*30,
						(j+1)*30,(i+1)*30);
			 
			if(A[i][j] != 0)
			{
				itoa(A[i][j],c,10);
				dc.TextOut(j*30+5,i*30+5,c);
			}
				brush.DeleteObject();
		}
	}

    itoa(num,c,10);
    dc.TextOut(100,220,c);
	
	t2=GetTickCount();

	itoa(int(t2-t1),c,10);
    dc.TextOut(100,250,c);
}

int CMyView::back_up(int ord,int x,int y)
{	
	if(ord == 12)
	{ 
		num++;
 
		    s();
			int w=1;
			w = MessageBox("   找到一个合适的拼图，\n按取消退出程序,确定继续运行","提示",1);				
		    if (w!=1)
			exit(0);

	
		return 1;
	}


	int p_k[13];
	int p_k_f[12][5];
	    
    Check_K(p_k,p_k_f,x,y);

	for(int i = 0;p_k[i]!=-1;i++)
	{
	    for(int j = 0;p_k_f[i][j]!=-1;j++)
		{
			put_k_A(p_k[i],p_k_f[i][j],x,y);
			Next(x,y);
			back_up(ord+1,x,y);
			Resume(p_k[i],p_k_f[i][j],x,y);
		}
	}
   return 1;
}


/////////////////////////////////////////////////////////////////////////////
// CMyView printing

BOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics

#ifdef _DEBUG
void CMyView::AssertValid() const
{
	CView::AssertValid();
}

void CMyView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
	return (CMyDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers


void CMyView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) 
{
	CView::OnKeyDown(nChar, nRepCnt, nFlags);

    int w;
	w = MessageBox("是否观看查找过程？(确定YES)(取消NO)","提示",1);
    if(w!=1)
    {
         show = 0;
	}
	else show = 1;
	t1=GetTickCount();
	back_up( 0, 0, 0);
	t2=GetTickCount();
}



void CMyView::OnRButtonUp(UINT nFlags, CPoint point) 
{
	CView::OnRButtonUp(nFlags, point);
    exit(0);
}

void CMyView::OnCancelMode() 
{
	CView::OnCancelMode();	
}