main.cpp

一个简单的华容道的算法；很适合初学者学习参考。

#include <iostream.h>

#include "point.h"
#include "Chess.h"
#include "ChessBoard.h"
#include "TreeList.h"
#include "TreeListNode.h"
#include "AVLTree.h"
#include "ListNode.h"
#include "time.h"
void main()
{
	clock_t star,finish;
	Chess ch[12] ;
/*	ch[0]=Chess(point(1,2),2);      //横
	ch[1]=Chess(point(0,0),1);      //刀
	ch[2]=Chess(point(3,0),1);      //立
	ch[3]=Chess(point(0,2),1);      //马
	ch[4]=Chess(point(3,2),1);      //棋
	ch[5]=Chess(point(1,0),4);      //盘
	ch[6]=Chess(point(1,3),3);      //表
	ch[7]=Chess(point(2,3),3);      //示
	ch[8]=Chess(point(0,4),3);      //  
	ch[9]=Chess(point(3,4),3);      //
	ch[10]=Chess(point(1,4),0);     //
	ch[11]=Chess(point(2,4),0);     //
*/

	ch[0]=Chess(point(0,0),2);      //横
	ch[1]=Chess(point(2,0),2);      //刀
	ch[2]=Chess(point(1,3),2);      //立
	ch[3]=Chess(point(0,1),1);      //马
	ch[4]=Chess(point(3,1),1);      //棋
	ch[5]=Chess(point(1,1),4);      //盘
	ch[6]=Chess(point(0,3),3);      //表
	ch[7]=Chess(point(3,3),3);      //示
	ch[8]=Chess(point(0,4),3);      //  
	ch[9]=Chess(point(3,4),3);      //
	ch[10]=Chess(point(1,4),0);     //
	ch[11]=Chess(point(2,4),0);     //



    ChessBoard cb=ChessBoard(ch,12), cb1, cb2;
	TreeList tl;
	AVLTree avlt;
	TreeListNode* tnode=new TreeListNode(cb);     //构造链表树根结点
	ListNode* ld = new ListNode(cb.GetHead(),cb.GetTail());//构造AVL树根结点
	tl.AddNode(tnode);         //将根结点加入到链表树中
	avlt.Insert(*ld);          //将根结点加入到AVL树中

/*	ListNode* ld=new ListNode(16,1);
	avlt.Insert(*ld);
	ld= new ListNode(3,1);
	avlt.Insert(*ld);
	ld= new ListNode(7,1);
	avlt.Insert(*ld);
	ld= new ListNode(11,1);
	avlt.Insert(*ld);
	ld= new ListNode(9,1);
	avlt.Insert(*ld);
	ld= new ListNode(26,5);
	avlt.Insert(*ld);
	ld= new ListNode(18,1);
	avlt.Insert(*ld);
	ld= new ListNode(14,1);
	avlt.Insert(*ld);
	ld= new ListNode(15,1);
	avlt.Insert(*ld);
	ld= new ListNode(9,1);
	avlt.Insert(*ld);
	ld= new ListNode(20,1);
	avlt.Insert(*ld);
	ld= new ListNode(19,1);
	avlt.Insert(*ld);
	ld= new ListNode(24,1);
	avlt.Insert(*ld);
	ld= new ListNode(32,1);
	avlt.Insert(*ld);
	ld= new ListNode(10,1);
	avlt.Insert(*ld);*/
	cout<<"OK"<<endl;
//	tl.AddNode(&tnode1);
//	tl.AddNode(&tnode2); 
	int k=0;
	bool flag = false;
//  while(!(tl.ptr->chbHead%32/8==1 && tl.ptr->chbHead%8==3) || !flag)
//	TreeListNode* tld;
//	ChessBoard cb1;
	star = clock();
	while(!flag)
    {
        if(tl.first!=tl.last)
        {
			cb = ChessBoard(tl.ptr->chbHead,tl.ptr->chbTail);//化数为盘
        }
        MoveMethod mmd[6];     //记录当前盘可行的移动方法
   		int j=0;
		for(int i=0; i<10; i++)
		{
			if(cb.CanUp(i))
			{
				mmd[j].Set(i,1);//第i个棋子可以向上移动
				j++;
			}
			if(cb.CanDown(i))
			{
				mmd[j].Set(i,2);
				j++;
			}
			if(cb.CanLeft(i))
			{
				mmd[j].Set(i,3);
				j++;
			}
			if(cb.CanRight(i))
			{
				mmd[j].Set(i,4);
				j++;
			}
		}
		j--;
		while(j>=0) //按可移动方法移动棋子
		{
    		ChessBoard cb1=cb;
			TreeListNode* tld;
			switch(mmd[j].method)
			{
			case 1:                                           //有棋子能上移  
				cb1.Up(mmd[j].chessNO);                       //将能上移的棋子上移
				if(cb1.chess[5].chessPosition.x == 1 && cb1.chess[5].chessPosition.y == 3)
				{
					flag = true;
				}
				ld = new ListNode(cb1.GetHead(),cb1.GetTail());
				if(avlt.Insert(*ld))
				{
					tld = new TreeListNode(cb1);                  //将移动后在盘面生成链表树结点
					tld->moveMethod = mmd[j];                     //将移动方法记入结点
					tl.AddNode(tld);                          //将链表树结点加入到链表树中
					tld->parent = tl.ptr;                     //将结点的指向链表树中当前指针所指结点,表示该结点由当前结点生成
				}
				else
				{
					delete  ld;
				}
				break;
			case 2:
				cb1.Down(mmd[j].chessNO);
				if(cb1.chess[5].chessPosition.x == 1 && cb1.chess[5].chessPosition.y == 3)
				{
					flag = true;
				}
				ld = new ListNode(cb1.GetHead(),cb1.GetTail());
				if(avlt.Insert(*ld))
				{
					tld = new TreeListNode(cb1);                  //将移动后在盘面生成链表树结点
					tld->moveMethod = mmd[j];                     //将移动方法记入结点
					tl.AddNode(tld);                          //将链表树结点加入到链表树中
					tld->parent = tl.ptr;                     //将结点的指向链表树中当前指针所指结点,表示该结点由当前结点生成
				}
				else
				{
					delete  ld;
				}
				break;
			case 3:
				cb1.Left(mmd[j].chessNO);
				if(cb1.chess[5].chessPosition.x == 1 && cb1.chess[5].chessPosition.y == 3)
				{
					flag = true;
				}
				ld = new ListNode(cb1.GetHead(),cb1.GetTail());
				if(avlt.Insert(*ld))
				{
					tld = new TreeListNode(cb1);                  //将移动后在盘面生成链表树结点
					tld->moveMethod = mmd[j];                     //将移动方法记入结点
					tl.AddNode(tld);                          //将链表树结点加入到链表树中
					tld->parent = tl.ptr;                     //将结点的指向链表树中当前指针所指结点,表示该结点由当前结点生成
				}
				else
				{
					delete  ld;
				}
				break;
			case 4:
				cb1.Right(mmd[j].chessNO);
				if(cb1.chess[5].chessPosition.x == 1 && cb1.chess[5].chessPosition.y == 3)
				{
					flag = true;
				}
				ld = new ListNode(cb1.GetHead(),cb1.GetTail());
				if(avlt.Insert(*ld))
				{
					tld = new TreeListNode(cb1);                  //将移动后在盘面生成链表树结点
					tld->moveMethod = mmd[j];                     //将移动方法记入结点
					tl.AddNode(tld);                          //将链表树结点加入到链表树中
					tld->parent = tl.ptr;                     //将结点的指向链表树中当前指针所指结点,表示该结点由当前结点生成
				}
				else
				{
					delete  ld;
				}
				break;
			}
			j--;						//准备解下一个可移动方法
		}
		tl.ptr=tl.ptr->next; //当前指针后移,进行第二步求解     	
        k++;  
		if( k%10000 == 0)
		{
			finish = clock();
			cout<<finish-star<<endl;
			cout<<"==============="<<endl;
		}
	}
	finish = clock();
	cout<<finish-star<<endl;
	TreeListNode *treel = tl.ptr;
	TreeListNode *treef = tl.first;
	int p=1;
	while(treel != tl.first)
	{
		cout<<p<<":";
		switch(treel->moveMethod.chessNO)
		{
		case 0:
			cout<<":关羽:->";break;
		case 1:
			cout<<"张飞:->";break;
		case 2:
			cout<<"赵云:->";break;
		case 3:
		    cout<<"马超:->";break;
		case 4:
			cout<<"黄忠:->";break;
		case 5:
			cout<<"曹操:->";break;
		case 6:
		case 7:
		case 8:
		case 9:
			cout<<"卒　:->";break;
		}
		switch(treel->moveMethod.method)
		{
		case 1:
			cout<<"上移!"<<"       ";break;
		case 2:
			cout<<"下移!"<<"       ";break;
		case 3:
			cout<<"左移!"<<"       ";break;
		case 4:
			cout<<"右移!"<<"       ";break;
		}
		cout<<endl;
		treel=treel->parent;
		p++;
	}
	cout<<k<<endl;
}