📄 mc.cpp
字号:
//-------------------------------------------------------------------------------------------------
//-------修道士野人问题的实现文件 作者：申徐洲 日期：2004年5月6日 AllRightsReserve
//-------------------------------------------------------------------------------------------------
#include "StdAfx.h"
#include ".\Mc.h"
//-------------------------------------------构造函数----------------------------------------------
CMissionarySavage::CMissionarySavage(void)
{
m_tDirection[0].x = 0; m_tDirection[0].y = 1;
m_tDirection[1].x = 0; m_tDirection[1].y = 2;
m_tDirection[2].x = 1; m_tDirection[2].y = 1;
m_tDirection[3].x = 1; m_tDirection[3].y = 0;
m_tDirection[4].x = 2; m_tDirection[4].y = 0;
m_pHead = new TMissionarySavage; // 头指针指向源结点
m_pHead->nMissionary = 3;
m_pHead->nSavage = 3;
m_pHead->nBoat = 1;
m_pHead->nDepth = 1;
m_pHead->nBreadth = 1;
m_pHead->nWeight = 4;
m_pHead->bIsSolution = false;
m_pHead->bIsVisited = false;
m_pHead->pParent = NULL;
m_pHead->pNext = NULL;
m_pHead->pSibling = NULL;
m_pTail = m_pHead; // 尾指针指向源结点
m_pLevel = new TMcLevel; // 第一层结点数是1
m_pLevel->nNodeNumber = 1;
m_pLevel->pLevel = m_pHead;
m_pLevel->pNext = NULL;
m_pLevelTail = m_pLevel;
m_nTotalNum = 1; // 初始化总结点数
m_nDepth = 1; // 初始化深度
m_pCurrent = m_pHead;
}
//----------------------------------------虚拟析构函数---------------------------------------------
CMissionarySavage::~CMissionarySavage(void)
{
while( m_pHead ) // 删除修道士野人问题的状态内存空间
{
m_pTail = m_pHead;
m_pHead = m_pHead->pNext;
delete( m_pTail );
}
while( m_pLevel ) // 删除修道士野人问题的第N层结点数量的内存空间
{
m_pLevelTail = m_pLevel;
m_pLevel = m_pLevel->pNext;
delete( m_pLevelTail );
}
}
//----------------------------------A*算法搜索修道士野人问题-----------------------------------------
bool CMissionarySavage::searchByAlgorithm(void)
{
TMissionarySavagePtr i_pTemp = m_pHead,i_pNew;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
i_pTemp = findMinCost();
if ( !i_pTemp )
return false;
if ( isGoal( i_pTemp ) )
{
findAnswer( i_pTemp);
return true;
}
for ( i_nDirection = 0; i_nDirection<5; i_nDirection++ )
if ( findNext( i_pTemp, i_nDirection ) ) // 判断下一状态是否合法
i_pNew = newMissionarySavage ( i_pTemp ,i_nDirection ) ;
if ( m_nTotalNum>4000 )
return false; // 如果结点总数大于1000 则认为该问题无解
i_pTemp = i_pTemp->pNext;
}
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
/*
//----------------------------------广度优先搜索八数码问题-----------------------------------------
bool CEightNumber::searchByBreadth(void)
{
if ( isGoal ( m_pHead ) ) // 如果源状态等于目标状态 则返回 true
{
findAnswer();
AfxMessageBox("恭喜你！算法成功");
return true;
}
TEightNumberPtr i_pTemp = m_pHead;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
for ( i_nDirection=0; i_nDirection<4; i_nDirection++ )
if ( findNext ( i_pTemp, i_nDirection ) ) // 按东南西北的顺序判判断下一状态是否合法
if( isGoal ( newEightNumber ( i_pTemp ,i_nDirection ) ) ) // 如果下一状态是目标状态
{
findAnswer(); // 找出八数码问题的正解
AfxMessageBox("恭喜你！算法成功");
return true;
}
if ( m_nTotalNum>4000 )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
i_pTemp = i_pTemp->pNext; // 指向下一个状态
}
AfxMessageBox("该问题无解 只显示前50步！");
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
//----------------------------------深度优先搜索八数码问题-----------------------------------------
bool CEightNumber::searchByDepth(void)
{
if ( isGoal ( m_pHead ) ) // 如果源状态等于目标状态 则返回 true
{
findAnswer();
AfxMessageBox("恭喜你！算法成功");
return true;
}
TEightNumberPtr i_pTemp = m_pHead;
int i_nDirection;
while ( i_pTemp ) // 如果仍有路径可寻
{
i_pTemp = findMaxDepth();
if ( !i_pTemp )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
for ( i_nDirection = 0; i_nDirection<4; i_nDirection++ )
if ( findNext( i_pTemp, i_nDirection ) ) // 按东南西北的顺序判判断下一状态是否合法
if( isGoal ( newEightNumber ( i_pTemp ,i_nDirection ) ) ) // 如果下一状态是目标状态
{
findAnswer(); // 找出八数码问题的正解
AfxMessageBox("恭喜你！算法成功");
return true;
}
if ( m_nTotalNum>4000 )
{
AfxMessageBox("算法失败 只显示前50步！");
return false; // 如果结点总数大于1000 则认为该问题无解
}
}
AfxMessageBox("该问题无解 只显示前50步！");
return false; // 如果所以路径走完仍没找到 则返回 fasle
}
*/
//------------------------------------显示修道士和野人的结果-------------------------------------
bool CMissionarySavage::show(CDC* pDC)
{
CPen i_greenPen, i_oldPen;
CBrush i_greenBrush, i_oldBrush;
int i_nDispLeftX=10, i_nDispRightX=550, i_nDispY=10; bool i_bIsFinished;
int i_nLeftMissionary,i_nLeftSavage,i_nRightMissionary,i_nRightSavage;
int i_nMissionary,i_nSavage,i_nTotalNum;
i_greenPen.CreatePen( PS_SOLID, 2, RGB( 0, 255, 0 ) );
i_oldPen.CreatePen( PS_SOLID, 1, RGB( 0, 0, 0 ) );
i_greenBrush.CreateSolidBrush( RGB( 0, 255, 0 ) );
i_oldBrush.CreateSolidBrush( RGB ( 255, 255, 255) );
if ( m_pCurrent )
{
if ( m_pCurrent == m_pHead ) // 如果是头指针
{
showPerson( pDC, 3, 3, i_nDispLeftX, i_nDispY );
m_pCurrent = m_pCurrent->pNext;
}
else
{
while ( !m_pCurrent->bIsSolution )
m_pCurrent = m_pCurrent->pNext;
if ( !m_bArriveShore )
{
if ( m_pCurrent->nBoat == -1 ) // 如果船在左岸
{
i_nLeftMissionary = m_pCurrent->nMissionary;
i_nLeftSavage = m_pCurrent->nSavage;
i_nRightMissionary = 3 - m_pCurrent->pParent->nMissionary;
i_nRightSavage = 3 - m_pCurrent->pParent->nSavage;
i_nMissionary = m_pCurrent->pParent->nMissionary - i_nLeftMissionary;
i_nSavage = m_pCurrent->pParent->nSavage - i_nLeftSavage;
i_nTotalNum = i_nMissionary + i_nSavage;
i_nDispLeftX=showPerson(pDC,i_nLeftMissionary,i_nLeftSavage,i_nDispLeftX,i_nDispY);
i_nDispRightX=showPerson(pDC,i_nRightMissionary,i_nRightSavage,i_nDispRightX,i_nDispY);
pDC->SelectObject( &i_oldPen ); pDC->SelectObject( &i_greenBrush );
pDC->Rectangle( i_nDispLeftX+m_nTimer+5,i_nDispY+42,i_nDispLeftX+m_nTimer+25*i_nTotalNum,i_nDispY+47 );
i_nDispLeftX=showPerson(pDC,i_nMissionary,i_nSavage,i_nDispLeftX+m_nTimer+5,i_nDispY);
m_nTimer += 10;
if ( i_nDispLeftX>540 )
m_bArriveShore = true;
}
else // 如果船在右岸
{
i_nLeftMissionary = m_pCurrent->pParent->nMissionary;
i_nLeftSavage = m_pCurrent->pParent->nSavage;
i_nRightMissionary = 3-m_pCurrent->nMissionary;
i_nRightSavage = 3-m_pCurrent->nSavage;
i_nMissionary = m_pCurrent->nMissionary - i_nLeftMissionary;
i_nSavage = m_pCurrent->nSavage - i_nLeftSavage;
i_nTotalNum = i_nMissionary + i_nSavage;
i_nDispLeftX=showPerson(pDC,i_nLeftMissionary,i_nLeftSavage,i_nDispLeftX,i_nDispY);
i_nDispRightX=showPerson(pDC,i_nRightMissionary,i_nRightSavage,i_nDispRightX,i_nDispY);
i_nDispRightX = 550; pDC->SelectObject(&i_oldPen); pDC->SelectObject(&i_greenBrush);
pDC->Rectangle( i_nDispRightX-m_nTimer-25*i_nTotalNum, i_nDispY+42 ,i_nDispRightX-m_nTimer-5, i_nDispY+47 );
i_nDispRightX=showPerson(pDC,i_nMissionary,i_nSavage,i_nDispRightX-m_nTimer-25*i_nTotalNum,i_nDispY);
m_nTimer += 10;
if ( i_nDispRightX-25*i_nTotalNum-10<i_nDispLeftX )
m_bArriveShore = true;
}
}
else // 如果船到达岸边
{
i_nLeftMissionary = m_pCurrent->nMissionary;
i_nRightMissionary = 3 - i_nLeftMissionary;
i_nLeftSavage = m_pCurrent->nSavage;
i_nRightSavage = 3 - i_nLeftSavage;
i_nDispLeftX=showPerson(pDC,i_nLeftMissionary,i_nLeftSavage,i_nDispLeftX,i_nDispY);
pDC->SelectObject( &i_oldPen ); pDC->SelectObject( &i_greenBrush );
if ( m_pCurrent->nBoat==1 )
pDC->Rectangle( i_nDispLeftX+5, i_nDispY+22, i_nDispLeftX+25, i_nDispY+27 );
else
pDC->Rectangle( 525, i_nDispY+22 ,545, i_nDispY+27 );
i_nDispRightX=showPerson(pDC,i_nRightMissionary,i_nRightSavage,i_nDispRightX,i_nDispY);
m_nTimer = 0;
m_bArriveShore = false;
m_pCurrent = m_pCurrent->pNext;
}
}
showPrompt( pDC );
i_bIsFinished = false;
}
else
i_bIsFinished = true;
return i_bIsFinished;
}
//----------------------------------------设置定时器初始状态-------------------------------------
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -