river.cpp

在VC的环境下

}

bool CRiver::R20()
{
	CRiver oldRiver = *this;
	
	if (RIGHT_BANK == m_nShipPos
		&& ((2==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] && 2==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]) 
		|| (1==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] && 3==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN])))
	{
		m_nShipPos = LEFT_BANK;
		m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] = m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] - 2;
		m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]= m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] + 2;

		if (NULL != m_pParent)
		{
			if (Compare(*m_pParent)
				&& m_nShipPos == m_pParent->m_nShipPos)
			{
				*this = oldRiver;
				return false;
			}
		}

		return true;
	}

	return false;
}

void main()
{
	bool bFinded = false;
	CRiver * pRiverOpenQueue[1024];
	int nHeadOpen = 0;
	int nRearOpen = 0;
	CRiver * pRiverClosedQueue[1024];
	int nHeadClosed = 0;
	int nRearClosed = 0;
	CRiver * pRiverS[1024];
	int nNo = -1;
	CRiver * pRiverCur = NULL;
	int i = 0;
	CRiver riverTemp;
	CRiver riverSg;
	
	// 初始化目标结点
	riverSg.m_nShipPos = CRiver::RIGHT_BANK;
	riverSg.m_pParent = NULL;
	for (i=0; i<2; i++)
	{
		riverSg.m_nChuchmenAndGoth[CRiver::LEFT_BANK][i] = 0;
		riverSg.m_nChuchmenAndGoth[CRiver::RIGHT_BANK][i] = 3;
	}
	
	// 初始化pRiverS
	for (i=0; i<1024; i++)
	{
		pRiverS[i] = NULL;
		pRiverOpenQueue[i] = NULL;
		pRiverClosedQueue[i] = NULL;
	}

	// 把S0放入OPEN表
	pRiverS[++nNo] = new CRiver;
	if (NULL == pRiverS[nNo])
	{
		cout<<"内存不足!"<<endl;
		exit(1);
	}
	if (nRearOpen < 1024) 
	{
		pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
	}

	while (nRearOpen > nHeadOpen) // OPEN表不为空
	{
		// 把第一个结点n，从OPEN表中移出，并把它放入CLOSED表中
		pRiverCur =  pRiverOpenQueue[nHeadOpen++];
		if (nRearClosed < 1024) 
		{
			pRiverClosedQueue[nRearClosed++] = pRiverCur;
		}

		// 扩展n，把它的后继结点放入OPEN表的末端，提供回到n的指针
		riverTemp = *pRiverCur;
		if (CRiver::LEFT_BANK == riverTemp.m_nShipPos)
		{
			if (riverTemp.L01())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}
		
				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.L10())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.L11())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.L02())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.L20())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
		}
		else
		{
			if (riverTemp.R01()) 
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.R10())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.R11())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.R02())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
			if (riverTemp.R20())
			{// 成功生成一个后继结点
				pRiverS[++nNo] = new CRiver;
				*pRiverS[nNo] = riverTemp;
				pRiverS[nNo]->m_pParent = pRiverCur;
				if (NULL == pRiverS[nNo])
				{
					cout<<"内存不足!"<<endl;
					exit(1);
				}
				if (nRearOpen < 1024) 
				{
					pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];
				}

				riverTemp = *pRiverCur;
				if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点
				{
					// 成功
					bFinded = true;
					break;
				}
			}
		}				
	}

	// 输出结果
	if (bFinded)
	{
		CRiver * riverP = NULL;
		pRiverS[nNo]->m_pNextStep = NULL;
		riverP = pRiverS[nNo];
		while (riverP->m_pParent != NULL)
		{
			(riverP->m_pParent)->m_pNextStep = riverP;
			riverP = riverP->m_pParent;
		}
		cout<<"计算机学院研8班沈枫："<<endl;
		while (riverP != NULL)
		{
//			int nShipPos = 0;
//			if (CRiver::LEFT_BANK == riverP->m_nShipPos)
//			{
//				nShipPos = 1;
//			}
//			
//			cout<<"(m, c, b): ";
//			cout<<"(";
//			cout<<riverP->m_nChuchmenAndGoth[CRiver::LEFT_BANK][CRiver::CHUCHMEN]<<", ";
//			cout<<riverP->m_nChuchmenAndGoth[CRiver::LEFT_BANK][CRiver::GOTH]<<", ";
//			cout<<nShipPos<<")"<<endl;
			cout<<*riverP<<endl;
			riverP = riverP->m_pNextStep;
		}
	}

	while (nNo > 0)
	{
		delete pRiverS[nNo];
		pRiverS[nNo] = NULL;
		nNo--;
	}
}