11dlg.cpp

图的遍历

// 11Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "11.h"
#include "11Dlg.h"
#include <stdio.h>
#include <malloc.h>
#include <stdlib.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()

/////////////////////////////////////////////////////////////////////////////
// CMy11Dlg dialog

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

void CMy11Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMy11Dlg)
	DDX_Control(pDX, IDC_LIST1, m_jieguo);
	DDX_Text(pDX, IDC_EDIT1, m_people);
	DDX_Text(pDX, IDC_EDIT2, m_boat);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMy11Dlg, CDialog)
	//{{AFX_MSG_MAP(CMy11Dlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMy11Dlg message handlers

BOOL CMy11Dlg::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 CMy11Dlg::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 CMy11Dlg::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 CMy11Dlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CMy11Dlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	
	CDialog::OnCancel();
}
typedef struct 
{
    int    zhengchangren;  //正常人
    int    huanzhe;   //精神病患者
    int    cw;         //船的位置
}DataType;           //表示当前状态的结构体

DataType fa[50000];

typedef struct node
{
    DataType data;
    struct node *son;
    struct node *bro;
    struct node *par;
    struct node *next;
}Ltable;      //定义的邻接表

void Ltableinit(Ltable **head)    //初始化邻接表的操作
{
    *head=(Ltable *)malloc(sizeof (Ltable));  //动态分配空间
    (*head)->son=NULL;
    (*head)->bro=NULL;
    (*head)->par=NULL;
    (*head)->next=NULL;
}

void insertson(Ltable *head, DataType x)   //在邻接表中插入儿子结点的操作
{
    Ltable *q,*s;
    q=(Ltable *)malloc(sizeof (Ltable));
    q->data=x;
    head->son=q;
    s=head;
    while (s->next!=NULL)
    s=s->next;
    q->par=head;
    q->son=NULL;
    q->bro=NULL;
    s->next=q;
    q->next=NULL;
}

void insertbro(Ltable *head,DataType x)     //在邻接表中插入兄弟结点的操作，所有的兄弟结点都指向他们右边的结点；
{
    Ltable *q,*s;
    q=(Ltable *)malloc(sizeof (Ltable));
    s=head->son;
    q->data=x;
    while (s->bro!=NULL)
       s=s->bro;
    s->bro=q;
    s->next=q;
    q->next=NULL;
    q->bro=NULL;
    q->par=head;
    q->son=NULL;
}


int findfa(DataType x,int n)     //生成在船上修道士仍安全的几种情况；
{
    int i=0,a,b,t=0;
    if(x.cw)
    {
       a=0;b=n-a; 
       while (a+b>=1)
           {
              t++;
              while (b>=0)
              {
                  fa[i].zhengchangren=a;
                  fa[i].huanzhe=b;
                  i++;
                  a++;
                  b--;
              }
              a=0;
              b=n-a-t;
           }
    }
    else
    {
       a=1;b=0;t=0;
       while (a+b<=n)
       {
           t++;
           while (a>=0)
           {                
              fa[i].zhengchangren=a*(-1);
              fa[i].huanzhe=b*(-1);
              i++;
              a--;
              b++;
           } 
           a=fa[0].zhengchangren*(-1)+t;
           b=0;
       }
    }
    return i;  
}


int jiancha(DataType x,int n)     //安全性检测，检查当前情况下，修道士是否安全
{
    if ((x.zhengchangren>=x.huanzhe||x.zhengchangren==0)&&((n-x.zhengchangren)>=(n-x.huanzhe)||x.zhengchangren==n)
		&&x.zhengchangren>=0&&x.zhengchangren<=n&&x.huanzhe>=0&&x.huanzhe<=n)
       return 1;
    else
       return 0;
}

void print(Ltable *q,Ltable *p)     //打印安全渡河的过程
{
 
}

//void work(Ltable *p,int n,int c)
//{
  
//}

void CMy11Dlg::OnOK() 
{
	UpdateData();
	char ttt[100];
    Ltable *p;
    DataType tem;
    Ltableinit(&p);        //初始化邻接表;
    int n=m_people;
	int c=m_boat;
  //  while (1)
  //  {
      // printf("请输入正常人和精神病患者的人数n:\n");
      // scanf("%d",&n);
      // if (n==0)
      //     break;
      // printf("请输入船可容纳的人数c:\n");
      // scanf("%d",&c);
       tem.zhengchangren=n;
       tem.huanzhe=n;
       tem.cw=1;
       insertson(p, tem);           //将初始状态作为头结点的孩子结点；
   Ltable *q,*t;
    DataType tem2;
    int i,flag,flag1,g=0,j,count=0,flag2=1;
    q=p->son;
    while (q!=NULL&&flag2)
    {
       flag=0;
        j=findfa(q->data,c);
        for (i=0;i<j;i++)
       {
           tem2.zhengchangren=q->data.zhengchangren-fa[i].zhengchangren;
           tem2.huanzhe=q->data.huanzhe-fa[i].huanzhe;
           tem2.cw=1-q->data.cw;
           t=q;
           if (jiancha (tem2,n))
           {
              flag1=1;
                while (t!=p)
              {
                  if(tem2.zhengchangren==t->data.zhengchangren&&tem2.huanzhe==t->data.huanzhe&&tem2.cw==t->data.cw)
                  {
                     flag1=0;
                     break;                
                  }
                  t=t->par;
              }
                if(flag1==1)
              {
                  if (flag==0)
                  {
                     insertson(q, tem2);
                     flag=1;
                  }
                  else
                           insertbro(q,tem2);                          
                  if (tem2.zhengchangren==0&&tem2.huanzhe==0&&tem2.cw==0)
                  {
                       DataType a[100];
                        int i=1;
                      a[0].cw=0;
                      a[0].zhengchangren=0;
                      a[0].huanzhe=0;
                      while (q!=p)
					  {
                         a[i++]=q->data;
                         q=q->par;
					  }
                     int k=i;
					  while ((--i)>-1)     
					  {
                        //	m_jieguo.AddString(ttt);
                        sprintf(ttt,"第%d步 ( %d %d %d )",k-i,a[i].zhengchangren,a[i].huanzhe,a[i].cw );
	                	m_jieguo.AddString(ttt);
                         if (!(a[i].zhengchangren==0&&a[i].huanzhe==0&&a[i].cw==0)) 
						 {
			              	  if (a[i].cw==1)
							  {
								  sprintf(ttt," --> ( %d %d ) --> ( %d  %d  0)\n",
		                          a[i].zhengchangren-a[i-1].zhengchangren,a[i].huanzhe-a[i-1].huanzhe,a[i-1].zhengchangren,a[i-1].huanzhe);
                                  m_jieguo.AddString(ttt);
							  }
							  else
							  {
				                   sprintf(ttt," --> ( %d %d ) --> ( %d  %d  1)\n",
		                           (a[i].zhengchangren-a[i-1].zhengchangren)*(-1),(-1)*(a[i].huanzhe-a[i-1].huanzhe),
		                           a[i-1].zhengchangren,a[i-1].huanzhe);
					               m_jieguo.AddString(ttt);
							  }
						 }
                      else
						  m_jieguo.AddString("\n");
					 }
                   m_jieguo.AddString("渡河成功!\n");
					  // print(q,p);
                    count++;
				  flag2=0;
                  }
              }          
           } 
       }  
       q=q->next;
    }  
    if (count==0)
       m_jieguo.AddString("无法成功渡河!\n");
    else
       m_jieguo.AddString("  \n");   
	   // work(p,n,c);                 //进行广度搜索；
 //   }
   
	UpdateData(FALSE);

	//CDialog::OnOK();
}