jinpeng.txt

三个野人和三个传教士要过河。 (1). 有三个野人和三个传教士要过河。 (2).只有一条船过河

// jinpengDlg.cpp : implementation file
//

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

/////////////////////////////////////////////////////////////////////////////
// CJinpengDlg dialog

CJinpengDlg::CJinpengDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CJinpengDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CJinpengDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CJinpengDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CJinpengDlg)
	DDX_Control(pDX, IDC_LIST1, m_list);
	//}}AFX_DATA_MAP
}

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

/////////////////////////////////////////////////////////////////////////////
// CJinpengDlg message handlers

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

void CJinpengDlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	
	CDialog::OnCancel();
}

void CJinpengDlg::OnOK() 
{
	// TODO: Add extra validation here
  #define   ChuanJiaoShi     3             /*定义传教士人数，可以随意修改，但要保证其>0，否则无意义，且程序运行错误*/   
  #define   YeRen                   3  
    /*定义问题所需数据结构：这是一个结构体，作为open表和close表的节点，具体参数参照后面的说明*/   
  typedef   struct   linknod   
  {   
  int   leftChuanJiaoShi;         /*左岸的传教士人数*/   
  int   leftYeRen;                       /*左岸的野人人数*/   
  int   rightChuanJiaoShi;       /*右岸的传教士人数*/   
  int   rightYeRen;                     /*右岸的野人人数*/   
  int   locationOfShip;             /*标志船在左岸还是右岸（左岸1，右岸0）*/   
  int   selfNumber;                     /*作为节点的序号*/   
  int   fatherNumber;                 /*记录他父亲的序号，目的是打印*/   
  struct   linknod   *next;         /*连接节点的next*/   
  }State;   
    
  State   *openHead;       /*open表的头节点*/   
  State   *closeHead;     /*close表的头节点*/
  State   *openF;     /*第一个节点*/   
  State   *openQ;     /*找到open表的第一个节点*/   
  State   *closeP;   /*从open表中移出的节点的内容作为closeP指针所指close链表节点的内容，   
                                  以头查式插入close链表   */   
  State   *openM;     /*预备以尾查式插入open表的节点指针*/   
  State   *openN;     /*变历open链表的指针*/   
  State   *closeN;   /*变历close链表的指针*/   
  State   *closeM;   /*打印时作为指向父亲的指针*/   
  State   *closeS;   /*打印时作为指向儿子的指针*/   
  State   *openS;     /*找open表的最后节点*/   

  int   tempLC;         /*左岸传教士数的临时变量*/   
  int   tempLY;         /*左岸野人数的临时变量*/   
  int   tempRC;         /*右岸传教士数的临时变量*/   
  int   tempRY;         /*右岸野人数的临时变量*/   
  int   tempLS;         /*标志左右岸的临时变量*/   
  int   tempSN;         /*记录自己序号的临时变量*/   
  int   tempFN;         /*记录父亲序号的临时变量*/   
  int   autoNumber=1;     /*从close表中扩展到open表时，给生成的节点取的序号记数器*/   
  int   i,j;                       /*双重循环的控制变量*/   
  int   lifeSafeFlag=0;   /*检验生命是否危险，及人数是否出现负数的标志(是：0,否:1)*/   
  int   openFlag=0;           /*检测open表中是否有新扩展预备节点的标志（有：1,无：0)*/   
  int   closeFlag=0;         /*检测close表中是否有新扩展预备节点的标志（有：1,无：0)*/   
  int   enter=1;  
  CString list;
  /*控制打印整齐的变量*/   
    
  /*控制打印清晰*/   
 // printf("\n-------------------------\n");   
    
        /*创建open表和close表，都是空表*/   
  openHead=(State*)malloc(sizeof(State));   
  openHead->next=NULL;   
  closeHead=(State*)malloc(sizeof(State));   
  closeHead->next=NULL;   
    
  /*创建初始节点，然后加到open表中，本来是加到open表的末尾，介于open表此时是空表，末尾和开头   
  　无区别，所以，加到open表的开头*/   
  openF=(State*)malloc(sizeof(State));   
  openF->leftChuanJiaoShi=ChuanJiaoShi;   
  openF->leftYeRen=YeRen;   
  openF->rightChuanJiaoShi=0;   
        openF->rightYeRen=0;   
        openF->locationOfShip=1;   
        openF->selfNumber=1;   
  openF->fatherNumber=0;   
        openF->next=openHead->next;   
  openHead->next=openF;   
  openF=NULL;         /*为内存安全*/   
          
  /*采取宽度优先搜索，先检查open表是否为空，空则失败退出。否则，从open表中取出节点，   
  　放到close表中，此时检验：是否是目标节点，是则成功，直接结束循环，打印。否则，对   
  　close表中的节点以(i,j)为(0,1)(0,2)(1,0)(1,1)(2,0)五种情况扩展到open表中，   
  　扩展方法：如果船在左岸，则扩展的节点是父节点的（左岸传教士数，左岸野人数）分别减上述   
  　5种情况，（右岸传教士数，右岸野人数）分别加上述5种情况，　如果船在右岸则相反处理。   
  　预备节点能否加到open表中取决于：是否安全和有意义；是否在open表出现过相同状态的节点；是否在close   
  　表出现过相同的状态的节点。接着返回循环。*/   
  while(1)   
  {         
  /*失败退出*/   
  if(openHead->next==NULL)   
  {   
  MessageBox("No   Way,Sorry!");   
  }   
  /*从open表中取出第一个节点（隐含删除）*/   
  openQ=openHead->next;   
  openHead->next=openQ->next;   
  tempLC=openQ->leftChuanJiaoShi;   
  tempLY=openQ->leftYeRen;   
  tempRC=openQ->rightChuanJiaoShi;   
  tempRY=openQ->rightYeRen;   
  tempLS=openQ->locationOfShip;   
  tempSN=openQ->selfNumber;   
  tempFN=openQ->fatherNumber;   
    
  free(openQ);/*释放内存*/   
    
                /*把从open表取出的节点加入close表的开头*/   
  closeP=(State*)malloc(sizeof(State));   
  closeP->leftChuanJiaoShi=tempLC;   
  closeP->leftYeRen=tempLY;   
  closeP->rightChuanJiaoShi=tempRC;   
  closeP->rightYeRen=tempRY;   
  closeP->locationOfShip=tempLS;   
  closeP->selfNumber=tempSN;   
  closeP->fatherNumber=tempFN;   
  closeP->next=closeHead->next;   
  closeHead->next=closeP;   
    
                /*如果出现目标，结束循环*/   
  if(tempLC==0&&tempLY==0&&tempRC==ChuanJiaoShi   
  &&tempRY==YeRen&&tempLS==0)   
  break;   
                  /**/   
  for(i=0;i<3;i++)   
  {   
  for(j=0;j<3;j++)   
  {   
  /*除去无意义的情况：船上无人，船上有３人，船上有４人*/   
  if(!(i==0&&j==0||i==1&&j==2||i==2&&j==1||i==2&&j==2))   
  {   
  openM=(State*)malloc(sizeof(State));   
    
  if(tempLS==0)     /*船在右岸的扩展方式*/   
  {   
  openM->leftChuanJiaoShi=tempLC+i;   
  openM->leftYeRen=tempLY+j;   
  openM->rightChuanJiaoShi=tempRC-i;   
  openM->rightYeRen=tempRY-j;   
  openM->locationOfShip=1;   
  }   
  else     /*船在左岸的扩展方式*/   
  {   
  openM->leftChuanJiaoShi=tempLC-i;   
  openM->leftYeRen=tempLY-j;   
  openM->rightChuanJiaoShi=tempRC+i;   
  openM->rightYeRen=tempRY+j;   
  openM->locationOfShip=0;   
  }   
    
                                        /*传教士生命安全吗？此节点中人数出现负数了吗？*/   
  if((openM->leftChuanJiaoShi>=openM->leftYeRen   
  &&openM->rightChuanJiaoShi>=openM->rightYeRen   
  ||openM->leftChuanJiaoShi==0   
  &&openM->rightChuanJiaoShi>=openM->rightYeRen   
  ||openM->leftChuanJiaoShi>=openM->leftYeRen   
  &&openM->rightChuanJiaoShi==0)   
  &&(openM->leftYeRen>=0&&openM->rightYeRen>=0))   
  lifeSafeFlag=1;   
  else   
  lifeSafeFlag=0;   
    
                                        /*open表中出现过和预备插入结点openM相同状态的节点吗？*/   
  openN=openHead;   
  while(openN->next!=NULL)   
  {   
  openN=openN->next;   
  if(openN->leftChuanJiaoShi==openM->leftChuanJiaoShi   
  &&openN->leftYeRen==openM->leftYeRen   
  &&openN->rightChuanJiaoShi==openM->rightChuanJiaoShi   
  &&openN->rightYeRen==openN->rightYeRen   
  &&openN->locationOfShip==openM->locationOfShip)   
  {   
  openFlag=1;   
  break;   
  }   
  else   
  {   
  openFlag=0;   
  }   
  }   
  openN=NULL;   
    
                                        /*close表中出现过和预备插入结点openM相同状态的节点吗？*/   
  closeN=closeHead;   
  while(closeN->next!=NULL)   
  {   
  closeN=closeN->next;   
  if(closeN->leftChuanJiaoShi==openM->leftChuanJiaoShi   
  &&closeN->leftYeRen==openM->leftYeRen   
  &&closeN->rightChuanJiaoShi==openM->rightChuanJiaoShi   
  &&closeN->rightYeRen==openM->rightYeRen   
  &&closeN->locationOfShip==openM->locationOfShip)   
  {   
  closeFlag=1;   
  break;   
  }   
  else   
  {   
  closeFlag=0;   
  }   
  }   
  closeN=NULL;/*内存安全*/   
    
                                        /*如果预备节点符合传教士生命安全，不出现负数，未在open表和close表中出现过，   
  　插入open表的末尾*/   
  if(lifeSafeFlag==1&&openFlag==0&&closeFlag==0)   
  {   
  openM->selfNumber=++autoNumber;   
  openM->fatherNumber=tempSN;   
  openS=openHead;
 
  while(openS->next!=NULL)   
  {   
  openS=openS->next;   
  }   
  openM->next=openS->next;   
  openS->next=openM;   
  openM=NULL;     /*内存安全*/   
  }   
  }   
  }   
  }   
  }   
    
        /*打印方法：用两个指针控制打印，closeM指向父亲，closeS指向自己，   
    判断如果closeS->fatherNumber==closeM->selfNumber,则打印出父节点   
    （注：先打印出儿子，后打印父亲）。enter变量控制打印整齐度。*/   
  closeM=closeHead->next;   
  closeS=closeM;
  
  m_list.AddString(list);
  list.Format(("%d,%d,%d,%d,%d"),closeM->leftChuanJiaoShi,closeM->leftYeRen,closeM->rightChuanJiaoShi,closeM->rightYeRen,closeM->locationOfShip);
  m_list.AddString(list);
  while(closeM->next!=NULL)   
  {   
  closeM=closeM->next;   
  if(closeS->fatherNumber==closeM->selfNumber)   
  {   
        enter++;
  list.Format(("<--%d,%d,%d,%d,%d"),closeM->leftChuanJiaoShi,closeM->leftYeRen,closeM->rightChuanJiaoShi,closeM->rightYeRen,closeM->locationOfShip);
  m_list.AddString(list);
  closeS=closeM;   
  }   
  }
  closeM=NULL;   
  closeS=NULL; 	
  MessageBox("恭喜你，聪明的传教士，成功过河！");
}