📄 mc.cpp
字号:
void CMissionarySavage::setTimer()
{
m_pCurrent = m_pHead;
m_nTimer = 0;
m_bArriveShore = false;
}
//-------------------------------------------获取结果链表----------------------------------------
TMissionarySavagePtr CMissionarySavage::getResultList(void)
{
return m_pHead;
}
//----------------------------------------获取结果总结点数量-------------------------------------
int CMissionarySavage::getResultNum(void)
{
return m_nTotalNum;
}
//-------------------------------------------获取结果深度----------------------------------------
int CMissionarySavage::getResultDepth(void)
{
return m_nDepth;
}
//--------------------------------判断当前状态是不是目标状态---------------------------------------
bool CMissionarySavage::isGoal(TMissionarySavagePtr pCurrent)
{
if ( pCurrent->nMissionary==0 && pCurrent->nSavage==0 && pCurrent->nBoat==-1 )
return true;
else
return false;
}
//-----------------------------------------新建结点------------------------------------------------
TMissionarySavagePtr CMissionarySavage::newMissionarySavage(TMissionarySavagePtr pParent, int nDirection)
{
TMissionarySavagePtr i_pNew;
TMcLevelPtr i_pLevel;
int i_nLeftMissionary, i_nLeftSavage, i_nBoat;
int i_nRowNum;
i_nLeftMissionary = pParent->nMissionary;
i_nLeftSavage = pParent->nSavage;
i_nBoat = pParent->nBoat;
i_nLeftMissionary = i_nLeftMissionary - m_tDirection[nDirection].x * i_nBoat;
i_nLeftSavage = i_nLeftSavage - m_tDirection[nDirection].y * i_nBoat;
i_nBoat = -i_nBoat;
i_pNew = new TMissionarySavage;
i_pNew->nMissionary = i_nLeftMissionary;
i_pNew->nSavage = i_nLeftSavage;
i_pNew->nBoat = i_nBoat;
i_pNew->nDepth = pParent->nDepth + 1;
if ( i_pNew->nDepth>m_nDepth ) // 如果深度增加
{
i_pNew->nBreadth = 1;
i_pLevel = new TMcLevel;
i_pLevel->nNodeNumber = 1;
i_pLevel->pLevel = NULL;
i_pLevel->pNext = NULL;
m_pLevelTail->pNext = i_pLevel;
m_pLevelTail = i_pLevel;
m_nDepth++; // 深度加1
}
else
{
i_pLevel = m_pLevel;
for ( i_nRowNum=1; i_nRowNum<m_nDepth; i_nRowNum++ )
i_pLevel = i_pLevel->pNext;
i_pLevel->nNodeNumber++;
i_pNew->nBreadth = i_pLevel->nNodeNumber;
}
i_pNew->nWeight = i_pNew->nDepth + i_nLeftMissionary + i_nLeftSavage - 2 * ( i_nBoat==1?1:0) - 1;
i_pNew->bIsSolution = false;
i_pNew->bIsVisited = false;
i_pNew->pParent = pParent;
i_pNew->pNext = NULL;
i_pNew->pSibling = NULL;
m_pTail->pNext = i_pNew; // 将新结点放入结点链表的尾部
m_pTail = i_pNew; // 对尾指针重新赋值
m_nTotalNum++; // 总结点数数量加1
return i_pNew;
}
//---------------------------------找出A*算法中代价最小的结点--------------------------------------
TMissionarySavagePtr CMissionarySavage::findMinCost(void)
{
TMissionarySavagePtr i_pTemp = m_pHead, i_pReturn = NULL;
int i_nWeight = 100;
while ( i_pTemp )
{
if ( !i_pTemp->bIsVisited )
if ( i_pTemp->nWeight < i_nWeight )
{
i_nWeight = i_pTemp->nWeight;
i_pReturn = i_pTemp;
}
i_pTemp = i_pTemp->pNext;
}
if ( i_pReturn )
i_pReturn->bIsVisited = true;
return i_pReturn;
}
//-------------------------------间断结点的下一个位置是否合法--------------------------------------
bool CMissionarySavage::findNext(TMissionarySavagePtr pCurrent, int nDirection)
{
int i_nLeftMissionary, i_nLeftSavage, i_nRightMissionary, i_nRightSavage, i_nBoat;
i_nLeftMissionary = pCurrent->nMissionary;
i_nLeftSavage = pCurrent->nSavage;
i_nBoat = pCurrent->nBoat;
i_nLeftMissionary = i_nLeftMissionary - m_tDirection[nDirection].x * i_nBoat;
i_nLeftSavage = i_nLeftSavage - m_tDirection[nDirection].y * i_nBoat;
i_nRightMissionary = 3 - i_nLeftMissionary;
i_nRightSavage = 3 - i_nLeftSavage;
i_nBoat = -i_nBoat;
if ( i_nLeftMissionary<0 || i_nLeftSavage<0 || i_nRightMissionary<0 || i_nRightSavage<0
|| ( i_nLeftMissionary<i_nLeftSavage && i_nLeftMissionary!=0 )
|| ( i_nRightMissionary<i_nRightSavage && i_nRightMissionary!=0 ) )
return false; // 如果下一个位置的数组维数越界 则返回 false
else
{ // 判断该结点是否已经存在
TMissionarySavagePtr i_pTemp;
bool i_bIsExist;
i_pTemp = m_pHead;
while ( i_pTemp )
{
i_bIsExist = true;
if ( i_pTemp->nMissionary != i_nLeftMissionary || i_pTemp->nSavage != i_nLeftSavage
|| i_pTemp->nBoat !=i_nBoat )
i_bIsExist = false;
if ( i_bIsExist )
break;
i_pTemp = i_pTemp->pNext;
}
return !i_bIsExist;
}
}
//------------------------------------找到八数码问题的解-------------------------------------------
void CMissionarySavage::findAnswer(TMissionarySavagePtr pMissionarySavage)
{
TMissionarySavagePtr i_pTemp;
i_pTemp = pMissionarySavage;
while ( i_pTemp )
{
i_pTemp->bIsSolution = true;
i_pTemp = i_pTemp->pParent;
}
}
//---------------------------------------显示修道士和野人----------------------------------------
int CMissionarySavage::showPerson(CDC* pDC, int nMissionary, int nSavage, int nDispX, int nDispY)
{
CPen i_redPen, i_greenPen, i_bluePen, i_oldPen;
CBrush i_redBrush, i_greenBrush, i_blueBrush, i_oldBrush;
int i_nNum; CPoint i_cPoint;
i_redPen.CreatePen( PS_SOLID, 2, RGB( 255, 0, 0 ) );
i_greenPen.CreatePen( PS_SOLID, 2, RGB( 0,255, 0 ) );
i_bluePen.CreatePen( PS_SOLID, 2, RGB( 0,0,255 ) );
i_oldPen.CreatePen( PS_SOLID, 1, RGB( 0, 0, 0 ) );
i_redBrush.CreateSolidBrush( RGB(255, 0, 0 ) );
i_greenBrush.CreateSolidBrush( RGB( 0, 255, 0 ) );
i_blueBrush.CreateSolidBrush( RGB( 0, 0, 255 ) );
i_oldBrush.CreateSolidBrush( RGB( 255, 255, 255 ) );
for ( i_nNum=0; i_nNum<nMissionary; i_nNum++ )
{
pDC->SelectObject( &i_redBrush );
pDC->SelectObject( &i_oldPen );
pDC->Ellipse( nDispX, nDispY, nDispX+20, nDispY+20 );
pDC->SelectObject( &i_oldBrush );
pDC->SelectObject( &i_redPen );
pDC->MoveTo( nDispX+10, nDispY+20 );
pDC->LineTo( nDispX+10, nDispY+30 );
pDC->MoveTo( nDispX, nDispY+25 );
pDC->LineTo( nDispX+20, nDispY+25 );
pDC->MoveTo( nDispX+10, nDispY+30 );
pDC->LineTo( nDispX, nDispY+40 );
pDC->MoveTo( nDispX+10, nDispY+30 );
pDC->LineTo( nDispX+20, nDispY+40 );
nDispX += 25;
}
for ( i_nNum=0; i_nNum<nSavage; i_nNum++ )
{
pDC->SelectObject( &i_blueBrush );
pDC->SelectObject( &i_oldPen );
pDC->Ellipse( nDispX, nDispY, nDispX+20, nDispY+20 );
pDC->SelectObject( &i_oldBrush );
pDC->SelectObject( &i_bluePen );
pDC->MoveTo( nDispX+10, nDispY+20 );
pDC->LineTo( nDispX+10, nDispY+30 );
pDC->MoveTo( nDispX, nDispY+25 );
pDC->LineTo( nDispX+20, nDispY+25 );
pDC->MoveTo( nDispX+10, nDispY+30 );
pDC->LineTo( nDispX, nDispY+40 );
pDC->MoveTo( nDispX+10, nDispY+30 );
pDC->LineTo( nDispX+20, nDispY+40 );
nDispX += 25;
}
pDC->SelectObject( &i_oldPen );
pDC->SelectObject( &i_oldBrush );
return nDispX;
}
//----------------------------------显示修道士和野人的状态提示-----------------------------------
void CMissionarySavage::showPrompt(CDC* pDC)
{
CPen i_redPen, i_greenPen, i_bluePen, i_oldPen;
CBrush i_redBrush, i_greenBrush, i_blueBrush, i_oldBrush;
i_redPen.CreatePen( PS_SOLID, 2, RGB( 255, 0, 0 ) );
i_greenPen.CreatePen( PS_SOLID, 2, RGB( 0, 255, 0 ) );
i_bluePen.CreatePen( PS_SOLID, 2, RGB( 0, 0, 255 ) );
i_oldPen.CreatePen( PS_SOLID, 1, RGB( 0, 0, 0 ) );
i_redBrush.CreateSolidBrush( RGB( 255, 0, 0 ) );
i_greenBrush.CreateSolidBrush( RGB( 0, 255, 0 ) );
i_blueBrush.CreateSolidBrush( RGB ( 0, 0, 255) );
i_oldBrush.CreateSolidBrush( RGB ( 255, 255, 255 ) );
pDC->SelectObject( &i_redBrush );
pDC->SelectObject( &i_oldPen );
pDC->Ellipse( 70, 70, 90 ,90 );
pDC->SelectObject( &i_redPen );
pDC->MoveTo( 80,90 ); pDC->LineTo( 80,100 );
pDC->MoveTo( 70,95 ); pDC->LineTo( 90,95 );
pDC->MoveTo( 80,100 ); pDC->LineTo( 70,110 );
pDC->MoveTo( 80,100 ); pDC->LineTo( 90,110 );
pDC->TextOut( 90,90, " ---- 修道士");
pDC->SelectObject( &i_blueBrush );
pDC->SelectObject( &i_oldPen );
pDC->Ellipse( 180, 70, 200 ,90 );
pDC->SelectObject( &i_bluePen );
pDC->MoveTo( 190,90 ); pDC->LineTo( 190,100 );
pDC->MoveTo( 180,95 ); pDC->LineTo( 200,95 );
pDC->MoveTo( 190,100 ); pDC->LineTo( 180,110 );
pDC->MoveTo( 190,100 ); pDC->LineTo( 200,110 );
pDC->TextOut( 200,90, " ---- 野人");
pDC->SelectObject( &i_greenBrush );
pDC->SelectObject( &i_oldPen );
pDC->Rectangle( 270, 95, 290 ,105 );
pDC->TextOut( 290,90, " ---- 船");
pDC->SelectObject( &i_oldPen );
pDC->SelectObject( &i_oldBrush );
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -