conway.cpp

一个经典的Conway游戏

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#define COL 7
#define LINE 8
#define INDEX 250000 
struct node
{
	char board[LINE][COL];
	struct  node *next;
};
typedef struct node aNode; 
struct node2
{
	aNode *board; 
	struct node2 *next;
	struct  node2 *previous;
};

typedef struct node2 pNode; 

pNode *InitpLink(pNode *p,aNode *a);
int InitpArray(aNode *a[]);
int GenerateIndex(char b[8][7]);         /*generate a hash value as array subscript*/
pNode *PrintqNode(pNode *qLastNode);        /*print the steps leading to the destiny*/
aNode *CreatNextStep(aNode *aCurrent);        /*generate the next step of the current board*/
pNode *AddtoLink(pNode *qLastNode,aNode *aNextStep,pNode *qCurrent,aNode *array[]);/*compare and add the next step to link*/ 
int main(int argc, char **argv)
{
	int x, y;
	if( argc==3 ){

		x=atoi(argv[1]);
		y=atoi(argv[2]);
	}
	else{
		printf("ERROR: Incorrect usage, try e.g. %s XXI\n", argv[0]);

		return 0;
	}

	int length=0,step=0,i,j,a,index;
	int weight[8][7];            /*calculate the steps to destiny*/
	for ( i = 0; i < LINE; i++)
		for ( j = 0; j < COL; j++) weight[i][j]=abs(x - i) + abs( y - j ); 
	aNode *array[INDEX];           /*creat a point array*/
	aNode *aNextStep, *aCurrent;
	index=InitpArray(array);          /*put the first board in the correspond place */

	pNode *qCurrent,*qLastNode,*qTempNode; 
	qCurrent=(pNode*)malloc(sizeof(pNode));
	if (qCurrent==NULL)
	{
		printf("cannot allocate Node\n");
		exit(2);
	}
	InitpLink(qCurrent,array[index]);
	qLastNode=qTempNode=qCurrent; 
	printf("Please wait...\n");
	while (qCurrent)            /*current board !=Null*/
	{
		aCurrent=qCurrent->board;
		for ( i=0; i<LINE; i++)          /*to find a soldier*/
		{
			for ( j=0; j<COL; j++)
			{
				if (aCurrent->board[i][j]=='1')
				{
					if ((i >= 2) && (aCurrent->board[i-1][j] == '1') && (aCurrent->board[i-2][j] =='0')&&(weight[i-2][j]<weight[i][j] )) /*jump up*/
					{      
						aNextStep=CreatNextStep(aCurrent);
						aNextStep->board[i][j] = '0';
						aNextStep->board[i-1][j] = '0';
						aNextStep->board[i-2][j] = '1';      
						qLastNode=AddtoLink(qLastNode,aNextStep,qCurrent,array);
						if ((i-2==x)&&(j==y))
						{
							PrintqNode(qLastNode);
							return 0;
						}
					}
					if ((j >= 2) && (aCurrent->board[i][j-1] == '1') && (aCurrent->board[i][j-2] == '0')&&(weight[i][j-2]<weight[i][j])) /*jump left*/
					{        
						aNextStep=CreatNextStep(aCurrent);
						aNextStep->board[i][j] = '0';
						aNextStep->board[i][j-1] = '0';
						aNextStep->board[i][j-2] = '1';      
						qLastNode=AddtoLink(qLastNode,aNextStep,qCurrent,array); 
						if ((i-2==x)&&(j==y))
						{
							PrintqNode(qLastNode);
							return 0;
						}
					}               
					if ((j <= 4) && (aCurrent->board[i][j+1] == '1') && (aCurrent->board[i][j+2] == '0')&&(weight[i][j+2]<weight[i][j])) /*jump right*/
					{         
						aNextStep=CreatNextStep(aCurrent);
						aNextStep->board[i][j] = '0';
						aNextStep->board[i][j+1] = '0';
						aNextStep->board[i][j+2] = '1';      
						qLastNode=AddtoLink(qLastNode,aNextStep,qCurrent,array);
						if ((i-2==x)&&(j==y))
						{
							PrintqNode(qLastNode);
							return 0;
						} 
					}
				}
			}
		} 
		qCurrent=qCurrent->next;  
	} 
	printf("No soldiar can go to the destiny\n\nPress anykey to quit\n");
	getchar();
	
	return 0;

} 

int GenerateIndex(char b[8][7])          /*generate index of point array*/         
{
	int i,j;
	double index=0;
	for ( i=0;i<LINE;i++)
		for ( j=0;j<COL;j++)
			if (b[i][j]=='1') index=index+pow(double(7*i+j) ,2);
	return (int)index;
} 
pNode *PrintqNode(pNode *qLastNode)
{
	int i,j;
	while (qLastNode!=NULL)
	{
		for ( i=0; i< LINE; i++)
		{
			printf("\n");
			for (j=0; j<COL;j++) 
				printf("%c",qLastNode->board->board[i][j]);   
		}
		qLastNode=qLastNode->previous;
		printf("\n");
	}
	printf("Press anykey to quit\n");
	getchar();
	return 0;
} 


int InitpArray(aNode **a)
{
	int i,j,index;
	aNode *aCurrent; 
	for ( index=0;index<INDEX;index++) 
	{
		a[index]=(aNode *)malloc(sizeof(aNode));
		if (a[index]==NULL)
		{
			printf("cannot allocate Node\n");
			exit(2);
		}
		for (i=0;i<LINE;i++)
		{
			for (j=0;j<COL;j++)
			{
				a[index]->board[i][j]=0;
				a[index]->next=NULL;
			}
		}
	} 
	aCurrent =(aNode *)malloc(sizeof(aNode));
	if (aCurrent==NULL)
	{
		printf("cannot allocate Node\n");
		exit(2);
	} 
	for ( i =0;i < 4; i++)
		for ( j = 0; j < 7; j++)  aCurrent->board[i][j] = '0';
	for ( i =4;i < 8; i++)
		for ( j = 0; j < 7; j++)  aCurrent->board[i][j] = '1'; 
	index=GenerateIndex(aCurrent->board);       /*add board to the point array*/
	aCurrent->next=a[index];
	a[index]=aCurrent;
	return index;
} 
pNode *InitpLink(pNode *qCurrent,aNode *a)
{ 
	qCurrent->board=a;
	qCurrent->next = NULL;
	qCurrent->previous= NULL;
	return qCurrent; 
} 

aNode *CreatNextStep(aNode *aCurrent)
{
	int i,j;
	aNode *aTempNode=(aNode *)malloc(sizeof(aNode));
	if (aTempNode==NULL)
	{
		printf("cannot allocate Node\n");
		exit(2);
	} 
	for ( i=0; i< LINE; i++)
		for ( j=0; j<COL;j++) 
			aTempNode->board[i][j]=aCurrent->board[i][j]; 
	aTempNode->next=NULL;
	return aTempNode;
} 
pNode *AddtoLink(pNode *qLastNode,aNode *aNextStep,pNode *qCurrent,aNode *array[])
{

	int cnt,i,j,index;
	aNode *atempNode;
	pNode *qTempNode;
	index=GenerateIndex(aNextStep->board);
	atempNode=array[index];          /*find if same board is already exists*/
	while (atempNode!=NULL)
	{
		cnt=0;
		for ( i=0; i< LINE; i++)
		{  
			for ( j=0; j<COL;j++) 
				if (aNextStep->board[i][j]!=atempNode->board[i][j])
				{
					atempNode=atempNode->next;
					i=10;
					j=10;
				} 
				else cnt++;
		}
		if (cnt==56)  
			return qLastNode;
	}
	aNextStep->next=array[index];        /*if not ,add to the array*/
	array[index]=aNextStep;
	qTempNode=(pNode*)malloc(sizeof(pNode));
	if (qTempNode==NULL)
	{
		printf("cannot allocate Node\n");
		exit(2);
	}
	qTempNode->board=array[index];        /*if not , add to the link*/
	qTempNode->next=NULL;
	qTempNode->previous=qCurrent;
	qLastNode->next=qTempNode;
	qLastNode=qLastNode->next;
	
	return qLastNode;
}