pp.cpp

九宫图游戏

		return false;
	if(study==true)
		Study(MOVE_UP);
	map[map[0]]=map[map[0]-3];
	map[map[0]-3]=0;
	map[0]-=3;//更改当前状态
	return true;
}
BOOL MoveLeft()
{
	if(map[0]==1||map[0]==4||map[0]==7)
		return false;
	if(study==true)
		Study(MOVE_LEFT);
	map[map[0]]=map[map[0]-1];
	map[map[0]-1]=0;
	map[0]-=1;
	return true;
}
BOOL MoveRight()
{
	if(map[0]==3||map[0]==6||map[0]==9)
		return false;
	if(study==true)
		Study(MOVE_RIGHT);
	map[map[0]]=map[map[0]+1];
	map[map[0]+1]=0;
	map[0]+=1;
	return true;
}
BOOL MoveBottom()
{
	if(map[0]==7||map[0]==8||map[0]==9)
		return false;
	if(study==true)
		Study(MOVE_DOWN);
	map[map[0]]=map[map[0]+3];
	map[map[0]+3]=0;
	map[0]+=3;
	return true;
}
int GetReverse()
{
	int i,j,re=0;
	for(i=1;i<9;i++)
		for(j=i+1;j<=9;j++)
			if(map[j]<map[i])
				re++;
	return re%2;
}
BOOL Success()
{
	for(int i=1;i<9;i++)
		if(map[i]!=i)
			return false;
	return true;
}
BOOL Search(int direct)
{
	BOOL result;
	int dir,dir2;
	switch(direct)
	{
	case MOVE_UP:
		result=MoveUp();
		break;
	case MOVE_DOWN:
		result=MoveBottom();
		break;
	case MOVE_LEFT:
		result=MoveLeft();
		break;
	case MOVE_RIGHT:
		result=MoveRight();
		break;//接受上层传来的方向，调用移动函数
	}
	if(result==false)//如动不了则返回
		return false;
	if(Push()==false)
	{
		switch(direct)
		{
		case MOVE_UP:
			result=MoveBottom();
			break;
		case MOVE_DOWN:
			result=MoveUp();
			break;
		case MOVE_LEFT:
			result=MoveRight();
			break;
		case MOVE_RIGHT:
			result=MoveLeft();
			break;//接受上层传来的方向，调用移动函数
		}
		return false;//当前状态压栈
	}
	//ReDraw();
	//Sleep(400);
	if(Success()==true)
		return true;
	dir=SearchKnowledge();//查找是否右已存状态
	if(dir==FAIL)//是否为已存的无解状态
	{
		MessageBox(hwnd,"当前游戏无解!!","提示",MB_OK);
		searching=false;
		ExitThread(0);
	}
	if(Search(dir)==true)
		return true;
	dir2=Judge();//在无已存状态时判断
	if(Search(dir2)==true)
		return true;
	if(direct != MOVE_DOWN && dir != MOVE_UP && dir2!=MOVE_UP)
		if(Search(MOVE_UP)==true)
			return true;
	if(direct != MOVE_RIGHT && dir != MOVE_LEFT && dir2!=MOVE_LEFT)
		if(Search(MOVE_LEFT)==true)
			return true;
	if(direct != MOVE_UP && dir != MOVE_DOWN && dir2!=MOVE_DOWN)
		if(Search(MOVE_DOWN)==true)
			return true;
	if(direct != MOVE_LEFT && dir != MOVE_RIGHT && dir2!=MOVE_RIGHT)
		if(Search(MOVE_RIGHT)==true)
			return true;
	//最后尝试其他各个方向

	Pop();
	return false;
}
BOOL Push()
{
	int *p=stack;
	int i=0;
	while(p!=stack_top)
	{
		if(p[i]==map[i])
		{
			i++;
			if(i==10)
				return false;
		}
		else
		{
			p=p+LEN;
			i=0;
		}
	}//查找是否右重复的状态，若有则不存，直接返回
	//这说明次状态已走过
	p=stack_top;
	for(i=0;i<10;i++)
		p[i]=map[i];
	stack_top+=LEN;
	len++;
	if(len==max_len)
	{
		stack=(int*)realloc(stack,sizeof(int)*(max_len+5000)*LEN);
		max_len=max_len+5000;
	}
	return true;
}
void  Pop()
{
	int i;
	stack_top-=LEN;
	len--;
	for(i=0;i<10;i++)
		map[i]=stack_top[i];
}
void ShowWaiting()
{
	HDC hdc;
	char text[30];
	hdc=GetDC(hwnd);
	while(searching==true)
	{
		sprintf(text,"Please Waiting........");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);
		sprintf(text,"Please Waiting.    ");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);
		sprintf(text,"Please Waiting..   ");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);
		sprintf(text,"Please Waiting...  ");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);
		sprintf(text,"Please Waiting.... ");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);
		sprintf(text,"Please Waiting.....");
		TextOut(hdc,230,325,text,21);
		sprintf(text,"Step Searched: %5ld",len);
		TextOut(hdc,230,345,text,20);
		Sleep(600);

//		sprintf(text,"Step Searched: %5ld",len);
//		TextOut(hdc,230,345,text,20);
	}
	sprintf(text,"Searching Finished");
	TextOut(hdc,230,325,text,18);
	ReleaseDC(hwnd,hdc);
}
void AutoSearch()
{
	int *p;
	BOOL result;
	if(study==true)
	{
		CloseStudy();
	}
//	OpenAutoFile();
	switch(SearchKnowledge())//先查找已存状态
	{
	case MOVE_UP:
		//
		result=Search(MOVE_UP);
		if(result==true)
		{
			goto success;
		}
		break;
	case MOVE_LEFT:
		//
		result=Search(MOVE_LEFT);
		if(result==true)
		{
			goto success;
		}
		break;
	case MOVE_RIGHT:
		//
		result=Search(MOVE_RIGHT);
		if(result==true)
		{
			goto success;
		}
		break;
	case MOVE_DOWN:
		//
		result=Search(MOVE_DOWN);
		if(result==true)
		{
			goto success;
		}
		break;
	default:
		//
		;
	}
	result=Search(MOVE_UP);
//	MessageBox(hwnd,"step1","ok",MB_OK);
	if(result==true)
	{
		goto success;
	}
	result=Search(MOVE_LEFT);//再试探其他方向
//	MessageBox(hwnd,"step2","ok",MB_OK);
	if(result==true)
	{
		goto success;
	}
	result=Search(MOVE_DOWN);
//	MessageBox(hwnd,"step3","ok",MB_OK);
	if(result==true)
	{
		goto success;
	}
	result=Search(MOVE_RIGHT);
//	MessageBox(hwnd,"step4","ok",MB_OK);
	if(result==true)
	{
		goto success;
	}
	searching=false;
	MessageBox(hwnd,"好像解不出来","失败",MB_OK);
	sign=STOP;//失败处理
//	CloseAutoFile();
	return;
success://成功处理
	searching=false;
//	CloseAutoFile();
	char pro[20];
	sprintf(pro,"演示开始(%ld步)\0",len);
	MessageBox(hwnd,pro,"成功",MB_OK);
	sign=DISPLAY;
	step=0;
	p=stack;
	while(p!=stack_top)//堆栈中存储的是已走过的步骤，所以从
						//堆栈中取出各状态进行演示
	{
		for(int i=0;i<10;i++)
			map[i]=p[i];
		step++;
		ReDraw();
		p=p+LEN;
		Sleep(playspeed);
	}
	MessageBox(hwnd,"演示结束","提示",MB_OK);
	sign=STOP;

}
void OpenStudy()
{
	study=true;
	HMENU hmenu;
	hmenu=GetMenu(hwnd);
	CheckMenuItem(hmenu,IDM_STUDY,MF_CHECKED);
}
void CloseStudy()
{
	study=false;
	HMENU hmenu;
	hmenu=GetMenu(hwnd);
	CheckMenuItem(hmenu,IDM_STUDY,MF_UNCHECKED);
}
void ReadKnowledge()
{//文件操作
	long i;
	if((fp=fopen("pdata.dat","r"))==NULL)
	{
		fp=fopen("pdata.dat","w");
		fprintf(fp,"%ld",0);
		fclose(fp);
		knowledge_top=knowledge=(int*)malloc(10000*sizeof(int)*(LEN+1));
		knowledge_len=0;
		return;
	}
	fscanf(fp,"%ld",&knowledge_len);
	if(knowledge_len==0)
	{
		knowledge_top=knowledge=(int*)malloc(10000*sizeof(int)*(LEN+1));
	}
	else
	{
		//count
		knowledge=(int*)malloc(10000*sizeof(int)*(LEN+1));
		fseek(fp,10L,0);
		fread(knowledge,sizeof(int),knowledge_len*(LEN+1),fp);
		knowledge_top=knowledge+knowledge_len*(LEN+1);
	}
	fclose(fp);
}
void SaveKnowledge()
{
	if(knowledge_len==0)
		return;
	fp=fopen("pdata.dat","w");
	fprintf(fp,"%ld",knowledge_len);
	fseek(fp,10L,0);
	fwrite(knowledge,sizeof(int),knowledge_len*(LEN+1),fp);
	fclose(fp);
	free(knowledge);
}
int SearchKnowledge()//再已存状态中搜索
{
	int *p;
	int i=0;
	p=knowledge;
	while(p!=knowledge_top)//Knowledge中数据为线性存储，11字节为一个单元
	{
		if(map[i]==p[i])
		{
			i++;
			if(i==10)
				return p[i];
		}
		else
		{
			p=p+LEN+1;
			i=0;
		}
	}
	return 0;
}
void Study(int direct)
{
	int dir,i;
	if((dir=SearchKnowledge())!=0)//如果现有知识中没有，则插入当前状态
		return;
	for(i=0;i<10;i++)
	{
		knowledge_top[i]=map[i];
	}
	knowledge_top[i]=direct;
	knowledge_top+=LEN+1;
	knowledge_len++;
}
int Judge()
{//判断，始终保持1，2两个方块再一起
	//此算法中搜索1、2两步，如搜索3不则速度很慢
	int i,direct;
	BOOL narrow;
	int pos[9];
	for(i=1;i<10;i++)
		pos[map[i]]=i;
	GetDistance(pos[1],pos[2],narrow,direct);
	{//判断1、2是否相连
		if(narrow==true)
		{
			GetDistance(pos[0],pos[2],narrow,direct);
			return direct;
		}
		else
		{
			GetDistance(pos[0],pos[1],narrow,direct);
			return direct;
		}
	}
}
void GetDistance(int pos1,int pos2,BOOL& narrow,int& direct)
{//根据位置序号判断位置关系，
	//narrow表示是否相连
	//direct表示pos1对于pos2的方向
	if((pos1-pos2)==3||(pos2-pos1)==3)
	{
		narrow=true;
		if(pos1>pos2)
			direct=MOVE_UP;
		else
			direct=MOVE_DOWN;
		return;
	}
	if(((pos1-pos2)==1&&pos1!=4&&pos1!=7)||((pos2-pos1)==1&&pos2!=4&&pos2!=7))
	{
		narrow=true;
		if(pos1>pos2)
			direct=MOVE_RIGHT;
		else
			direct=MOVE_LEFT;
		return;
	}
	narrow=false;
	if(pos1%3>pos2%3)
	{
		direct=MOVE_RIGHT;
		return;
	}
	else if(pos1%3<pos2%3)
	{
		direct=MOVE_LEFT;
		return;
	}
	else
	{
		if(pos1>pos2)
		{
			direct=MOVE_UP;
			return;
		}
		else
		{
			direct=MOVE_DOWN;
			return;
		}
	}
}