riverdlg.cpp

警察小偷爸爸妈妈儿子女儿过河

// RiverDlg.cpp : implementation file
//

#include "stdafx.h"
#include "River.h"
#include "RiverDlg.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()

/////////////////////////////////////////////////////////////////////////////
// CRiverDlg dialog

CRiverDlg::CRiverDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CRiverDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CRiverDlg)
	m_nGoEnd = 0;
	m_nGoBegin = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CRiverDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CRiverDlg)
	DDX_Control(pDX, IDC_MOVESTEP, m_ListStep);
	DDX_Control(pDX, IDC_MYROAD, m_ListMyRoad);
	DDX_Control(pDX, IDC_ROOT, m_ListRoot);
	DDX_Text(pDX, IDC_GOEND, m_nGoEnd);
	DDX_Text(pDX, IDC_GOBEGIN, m_nGoBegin);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CRiverDlg, CDialog)
	//{{AFX_MSG_MAP(CRiverDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_RIVER, OnRiver)
	ON_BN_CLICKED(IDC_PARSE, OnParse)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CRiverDlg message handlers

BOOL CRiverDlg::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
	m_bEndFlag = FALSE;
	m_ListRoot.InsertColumn(0,"第几个节点", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(1,"父亲位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(2,"母亲位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(3,"女儿1位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(4,"女儿2位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(5,"儿子1位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(6,"儿子2位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(7,"警察位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(8,"歹徒位置", LVCFMT_LEFT,60);
	m_ListRoot.InsertColumn(9,"船的位置", LVCFMT_LEFT,60);

	m_ListMyRoad.InsertColumn(0,"第几条路", LVCFMT_LEFT,60);
	m_ListMyRoad.InsertColumn(1,"如何走", LVCFMT_LEFT,60);

	m_ListStep.InsertColumn(0,"步骤", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(1,"父亲位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(2,"母亲位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(3,"女儿1位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(4,"女儿2位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(5,"儿子1位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(6,"儿子2位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(7,"警察位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(8,"歹徒位置", LVCFMT_LEFT,60);
	m_ListStep.InsertColumn(9,"船的位置", LVCFMT_LEFT,60);


	///////////////////////////////////////////////////////
	DWORD dwStyleEx;
	//LVS_SINGLESEL
	dwStyleEx = LVS_EX_FULLROWSELECT | LVS_REPORT |  LVS_EX_ONECLICKACTIVATE; 
	m_ListMyRoad.SetExtendedStyle( dwStyleEx );
	m_ListRoot.SetExtendedStyle( dwStyleEx );
	m_ListStep.SetExtendedStyle( dwStyleEx );
	

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

void CRiverDlg::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 CRiverDlg::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();
	}
}

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

void CRiverDlg::OnRiver() 
{
	// TODO: Add your control notification handler code here
	UpdateData();
	if(m_nGoEnd > m_wheres.GetSize()-1)
	{
		MessageBox("填入数字错误,这种情况不存在");
		return;
	}

	m_bEndFlag = FALSE;			//重置结束标志
	m_ListStep.DeleteAllItems();
	m_ListStep.SetRedraw(FALSE);
	
	int i(0);
	int nItem(0);
	CString strInfo;

	//声明结点访问标志
	BOOL *Visited = new BOOL[m_wheres.GetSize()];
	for(i = 0 ; i<m_wheres.GetSize(); i++)
		Visited[i] = FALSE;
	//初始化道路
	
	CArray<int, int> Road;

	//遍历找到结点
	GoRiver(Road, m_nGoBegin, m_nGoEnd, m_MoveAll, Visited);
	CString saMessage[3] = {"左岸","船上","右岸"};
	nItem = 0;
	for(i = 0; i<Road.GetSize(); i++)
	{
		strInfo.Format("第%d步", i+1);
		nItem = m_ListStep.InsertItem(nItem, strInfo);
		m_ListStep.SetItemText(nItem, 0, strInfo);
		m_ListStep.SetItemText(nItem, 1, saMessage[m_wheres.GetAt(Road.GetAt(i)).father-1]);
		m_ListStep.SetItemText(nItem, 2, saMessage[m_wheres.GetAt(Road.GetAt(i)).mother-1]);
		m_ListStep.SetItemText(nItem, 3, saMessage[m_wheres.GetAt(Road.GetAt(i)).daughter1-1]);
		m_ListStep.SetItemText(nItem, 4, saMessage[m_wheres.GetAt(Road.GetAt(i)).daughter2-1]);
		m_ListStep.SetItemText(nItem, 5, saMessage[m_wheres.GetAt(Road.GetAt(i)).son1-1]);
		m_ListStep.SetItemText(nItem, 6, saMessage[m_wheres.GetAt(Road.GetAt(i)).son2-1]);
		m_ListStep.SetItemText(nItem, 7, saMessage[m_wheres.GetAt(Road.GetAt(i)).plice-1]);
		m_ListStep.SetItemText(nItem, 8, saMessage[m_wheres.GetAt(Road.GetAt(i)).shife-1]);
		m_ListStep.SetItemText(nItem, 9, saMessage[m_wheres.GetAt(Road.GetAt(i)).boat-1]);
		nItem++;
	}

	delete[] Visited;
	m_ListStep.SetRedraw(TRUE);
	m_ListStep.Invalidate();
	
}

void CRiverDlg::GoRiver(CArray<int,int>& p_Road, int Begin, int End, CArray<Move, Move>& p_MoveAll, BOOL *Visited)
{
	//深度遍历图形算法
	//此步不需要因为从设置了结束位以后就再也没调用GORIVER了
	//if(m_bEndFlag) return;
	int i;
	Visited[Begin] = TRUE;
	//讲其加入到走过的路中
	p_Road.Add(Begin);
	if(Begin == End)
	{
		m_bEndFlag = TRUE;
		MessageBox("找到了从起点通往终点道路");
		return;
	}
	
	for(i=0; i<p_MoveAll.GetSize(); i++)
	{
		if(p_MoveAll.GetAt(i).m_nNow == Begin)
		{
			if(Visited[p_MoveAll.GetAt(i).m_nNext] == FALSE)
			{
				GoRiver(p_Road, p_MoveAll.GetAt(i).m_nNext, End, p_MoveAll, Visited);
				if(m_bEndFlag) return;
			}
		}
	}

	//如果遍历完了还没找到说明此路不通出栈
	p_Road.RemoveAt(p_Road.GetSize()-1);

	

}

void CRiverDlg::OnParse() 
{
	//找的所有的状态结点位置及所有可以走过的路
	// TODO: Add your control notification handler code here
	CString strInfo;//信息提示
	m_ListRoot.DeleteAllItems();//ROOT清空
	m_ListMyRoad.DeleteAllItems();//MYROAD清空
	m_wheres.RemoveAll();  //结点清空
	
	InWhere where;			//临时结点
	m_ListRoot.SetRedraw(FALSE); //不许重绘图
	int AccordNum(0); //序号
	int nItem(0);
	int i,j,k,l,m,n,o,p,q;
	for(i=1; i<4; i++)
		for(j=1; j<4; j++)
			for(k=1; k<4; k++)
				for(l=1; l<4; l++)
					for(m=1; m<4; m++)
						for(n=1; n<4; n++)
							for(o=1; o<4; o++)
								for(p=1; p<4; p++)
									for(q = 1; q<4; q++)
									{
										where.daughter1 = i;
										where.daughter2 = j;
										where.father = k;
										where.mother = l;
										where.plice = m;
										where.shife = n;
										where.son1 = o;
										where.son2 = p;
										where.boat = q;

										if(where.Test())
										{
											strInfo.Format("%d", AccordNum);
											nItem = m_ListRoot.InsertItem(nItem, strInfo);
											m_ListRoot.SetItemText(nItem,0,strInfo);
											strInfo.Format("%d", k);
											m_ListRoot.SetItemText(nItem,1,strInfo);
											strInfo.Format("%d", l);
											m_ListRoot.SetItemText(nItem,2,strInfo);
											strInfo.Format("%d", i);
											m_ListRoot.SetItemText(nItem,3,strInfo);
											strInfo.Format("%d", j);
											m_ListRoot.SetItemText(nItem,4,strInfo);
											strInfo.Format("%d", o);
											m_ListRoot.SetItemText(nItem,5,strInfo);
											strInfo.Format("%d", p);
											m_ListRoot.SetItemText(nItem,6,strInfo);
											strInfo.Format("%d", m);
											m_ListRoot.SetItemText(nItem,7,strInfo);
											strInfo.Format("%d", n);
											m_ListRoot.SetItemText(nItem,8,strInfo);
											strInfo.Format("%d", q);
											m_ListRoot.SetItemText(nItem,9,strInfo);

											m_wheres.Add(where);
											++AccordNum;
											++nItem;
										}
									}
		m_ListRoot.SetRedraw(TRUE);
		m_ListRoot.Invalidate();
		m_ListMyRoad.SetRedraw(FALSE);

		strInfo.Format("一共有%d种可能状况", m_wheres.GetSize());
		MessageBox(strInfo);

		m_MoveAll.RemoveAll();
		Move mov;
		AccordNum = 0;
		nItem = 0;
		for(i = 0; i< m_wheres.GetSize(); i++)
			for(j = 0; j< m_wheres.GetSize(); j++)
			{
				mov.m_nNow = i;
				mov.m_nNext = j;
				if(i != j && mov.Test(m_wheres))
				{
					strInfo.Format("%d", AccordNum);
					nItem = m_ListMyRoad.InsertItem(nItem, strInfo);
					m_ListMyRoad.SetItemText(nItem,0,strInfo);
					strInfo.Format("%d->%d", i,j);
					m_ListMyRoad.SetItemText(nItem,1,strInfo);
					m_MoveAll.Add(mov);
					++AccordNum;
					++nItem;
				}
			}
			m_ListMyRoad.SetRedraw(TRUE);
			m_ListMyRoad.Invalidate();

		strInfo.Format("一共有%d种可能移动状况", m_MoveAll.GetSize());
		MessageBox(strInfo);
		GetDlgItem(IDC_RIVER)->EnableWindow();
		GetDlgItem(IDC_GOEND)->EnableWindow();
		GetDlgItem(IDC_GOBEGIN)->EnableWindow();
		//设默认值为起点0终点最后m_wheres的最后个
		//设置默认的起点和终点
		m_nGoBegin = 0;
		m_nGoEnd = m_wheres.GetSize()-1;
		UpdateData(FALSE);
}