bsmdlg.cpp

一个很经典的问题_八数码! 算法速度快,解决问题多...有兴趣的可以

// BSMDlg.cpp : implementation file
//

#include "stdafx.h"
#include "BSM.h"
#include "BSMDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBSMDlg dialog

CBSMDlg::CBSMDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CBSMDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CBSMDlg)
	m_end1 = _T("1");
	m_end2 = _T("2");
	m_end3 = _T("3");
	m_end4 = _T("4");
	m_end5 = _T("5");
	m_end6 = _T("6");
	m_end7 = _T("7");
	m_end8 = _T("8");
	m_end9=  _T("0");
	m_ori1 = 2;
	m_ori2 = 0;
	m_ori3 = 3;
	m_ori4 = 1;
	m_ori5 = 8;
	m_ori6 = 5;
	m_ori7 = 4;
	m_ori8 = 7;
	m_ori9 = 6;
	step=0;
	
	
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CBSMDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CBSMDlg)
	DDX_Text(pDX, IDC_END1, m_end1);
	DDX_Text(pDX, IDC_END2, m_end2);
	DDX_Text(pDX, IDC_END3, m_end3);
	DDX_Text(pDX, IDC_END4, m_end4);
	DDX_Text(pDX, IDC_END5, m_end5);
	DDX_Text(pDX, IDC_END6, m_end6);
	DDX_Text(pDX, IDC_END7, m_end7);
	DDX_Text(pDX, IDC_END8, m_end8);
	DDX_Text(pDX, IDC_END9, m_end9);
	DDX_Text(pDX, IDC_START1, m_ori1);
	DDX_Text(pDX, IDC_START2, m_ori2);
	DDX_Text(pDX, IDC_START3, m_ori3);
	DDX_Text(pDX, IDC_START4, m_ori4);
	DDX_Text(pDX, IDC_START5, m_ori5);
	DDX_Text(pDX, IDC_START6, m_ori6);
	DDX_Text(pDX, IDC_START7, m_ori7);
	DDX_Text(pDX, IDC_START8, m_ori8);
	DDX_Text(pDX, IDC_START9, m_ori9);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CBSMDlg, CDialog)
	//{{AFX_MSG_MAP(CBSMDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_RAND, OnRand)
	ON_BN_CLICKED(IDC_QIFA, OnQifa)
	ON_BN_CLICKED(IDC_STARTEND, OnStartend)
	ON_BN_CLICKED(IDC_GUANGDU, OnGuangdu)
	ON_BN_CLICKED(IDC_KUANDU, OnShendu)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBSMDlg message handlers

BOOL CBSMDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here


	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CBSMDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CBSMDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
/*	m_ori1=m_byBoard[0][0];
	m_ori2=m_byBoard[0][1];
	m_ori3=m_byBoard[0][2];
	m_ori4=m_byBoard[1][0];
	m_ori5=m_byBoard[1][1];
	m_ori6=m_byBoard[1][2];
	m_ori7=m_byBoard[2][0];
	m_ori8=m_byBoard[2][1];
	m_ori9=m_byBoard[2][2];
	UpdateData();*/
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CBSMDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CBSMDlg::OnRand() 
{
	// TODO: Add your control notification handler code here
	int i,j,k=0;
	int a[9];

	srand((unsigned)time(NULL));
	for(i=0;i<9;i++)
	{
		a[i]=rand()%9;
		do					
		a[i]=rand()%9;
		while(IsIn(a,i));
	}

	m_ori1=a[0];
	m_ori2=a[1];
	m_ori3=a[2];
	m_ori4=a[3];
	m_ori5=a[4];
	m_ori6=a[5];
	m_ori7=a[6];
	m_ori8=a[7];
	m_ori9=a[8];
	


	UpdateData(false);

//	UpdateBoard(m_byBoard);
	
}

bool CBSMDlg::IsIn(int a[], int i)
{
	for(int j=0;j<i;j++)
		if(a[j]==a[i])
			return 1;

	return 0;

}



BOOL CBSMDlg::OnQifa() 
{
	// TODO: Add your control notification handler code here

    EightNum S(m_byBoard),Target(m_target);
	int flag=0;
	S.parent=S.leaf_next=S.leaf_pre=NULL;
	S.cul_para();
	
	
	
	if(!icansolve(m_byBoard,m_target))
	{
		
		GetDlgItem(IDC_EDIT_STATION)->SetWindowText("Fail!No one can do it !");

		return FALSE;
		
	}
	clock_t Start,finish;
	double duration;

	Start=clock( );

	EightNum *OK_leaf=&S,*leaf_start=&S,*new_8num,*p;
	while(OK_leaf!=NULL&&flag!=1)
	{
		OK_leaf=find_OK_leaf(leaf_start);
		
		
		if(*OK_leaf==Target)
		{
			flag=1;
			break;
		}
		
		p=OK_leaf->leaf_pre;
		OK_leaf->get_numbers_to(m_byBoard);
	/*	m_ori1=m_byBoard[0];
		m_ori2=m_byBoard[1];
		m_ori3=m_byBoard[2];
		m_ori4=m_byBoard[3];
		m_ori5=m_byBoard[4];
		m_ori6=m_byBoard[5];
		m_ori7=m_byBoard[6];
		m_ori8=m_byBoard[7];
		m_ori9=m_byBoard[8];
		m_str1.Format("\r\nthe %d step is:\r\n%d  %d  %d\r\n%d  %d  %d\r\n%d  %d  %d",step,m_ori1,m_ori2,m_ori3,m_ori4,m_ori5,m_ori6,m_ori7,m_ori8,m_ori9);
		m_str2+=m_str1;
		GetDlgItem(IDC_EDIT_STATION)->SetWindowText(m_str2);

	
		UpdateData();*/
		if(move_up(m_byBoard)&&!existed(m_byBoard,OK_leaf))
		{
			new_8num=new EightNum;			
			new_8num->set_num(m_byBoard);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			
		}
		OK_leaf->get_numbers_to(m_byBoard);
		if(move_down(m_byBoard)&&!existed(m_byBoard,OK_leaf))
		{
			new_8num=new EightNum;			
			new_8num->set_num(m_byBoard);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			
		}
		OK_leaf->get_numbers_to(m_byBoard);
		if(move_left(m_byBoard)&&!existed(m_byBoard,OK_leaf))
		{
			new_8num=new EightNum;			
			new_8num->set_num(m_byBoard);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
		
		}
		OK_leaf->get_numbers_to(m_byBoard);
		if(move_right(m_byBoard)&&!existed(m_byBoard,OK_leaf))
		{
			new_8num=new EightNum;			
			new_8num->set_num(m_byBoard);
			new_8num->parent=OK_leaf;
			new_8num->cul_para();
			new_8num->leaf_pre=p;
			if(p==NULL)
				leaf_start=new_8num;
			else
				p->leaf_next=new_8num;
			p=new_8num;
			
		}
		p->leaf_next=OK_leaf->leaf_next;
		if(OK_leaf->leaf_next!=NULL)
			OK_leaf->leaf_next->leaf_pre=p;
		OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;
	}
	finish=clock( ); 
	duration=finish-Start;
	
	if(flag==1)
	{
		EightNum *p;
		for (p=OK_leaf->parent;p!=NULL;p=p->parent)
		{
			step++;
			p->get_numbers_to(m_byBoard);
			m_ori1=m_byBoard[0];
			m_ori2=m_byBoard[1];
			m_ori3=m_byBoard[2];
			m_ori4=m_byBoard[3];
			m_ori5=m_byBoard[4];
			m_ori6=m_byBoard[5];
			m_ori7=m_byBoard[6];
			m_ori8=m_byBoard[7];
			m_ori9=m_byBoard[8];
			m_str1.Format("\r\nthe %d step is:\r\n%d  %d  %d\r\n%d  %d  %d\r\n%d  %d  %d",step,m_ori1,m_ori2,m_ori3,m_ori4,m_ori5,m_ori6,m_ori7,m_ori8,m_ori9);
			m_str2+=m_str1;
			GetDlgItem(IDC_EDIT_STATION)->SetWindowText(m_str2);
			
		
		}
		m_str3.Format("\r\nCongratulation!the time is %f ms",duration);//"\r\nthe last step is:\r\n"+m_end1+"  "+m_end2+"  "+m_end3+"\r\n"+m_end4+"  "+m_end5+"  "+m_end6+"\r\n"+m_end7+"  "+m_end8+"  "+m_end9;