📄 6-3.c

📁 一本经典书籍--C程序员成长攻略的原代码
💻 C
📖 第 1 页 / 共 2 页
字号:
上一页 12
EXIT:
	return c_y;
}

/*进行子菜单选择，设置难度difficulty。函数返回选项条所在y坐标值*/
int F2_CHOOSE()
{ 
	char ch;
	int c_x=WIN_X,c_y=WIN_Y+FILE_H*3;
	CHOIC(c_x,c_y,BK_COLOR);
	CHOIC(c_x+FILE_L,c_y,CHOIC_COLOR);
	MENU2();  
	while(1)
	{ 
		if(kbhit())
		{ 
			ch=getch();
			if(ch==ESC) 
			{ 
				Clear_FILE2(); 
				CHOIC(WIN_X,WIN_Y+FILE_H*3,CHOIC_COLOR);
				C_CHOOSE(); 
				break;
			}
			if(ch==Enter) 
			{ 
				switch(c_y)  
				{
				case WIN_Y+FILE_H*3: 
					n=N1; 
					difficulty=LatticeAmount1; 
					break;
				case WIN_Y+FILE_H*4: 
					n=N2; 
					difficulty=LatticeAmount2; 
					break;
				};
				Clear_BG(); 
				MENU1();
				CHOIC(WIN_X,WIN_Y+FILE_H*3,CHOIC_COLOR);
				C_CHOOSE(); 
				break;
			}
			if(ch==upkey)  
			{ 
				CHOIC(c_x+FILE_L,c_y,BK_COLOR);
				if(c_y==WIN_Y+FILE_H*3)  
					c_y=WIN_Y+FILE_H*4;
				else 
					c_y-=FILE_H;
				CHOIC(c_x+FILE_L,c_y,CHOIC_COLOR);
				C_9(); 
				C_16();
			}
			if(ch==downkey)
			{ 
				CHOIC(c_x+FILE_L,c_y,BK_COLOR);
				if(c_y==WIN_Y+FILE_H*4) 
					c_y=WIN_Y+FILE_H*3;
				else 
					c_y+=FILE_H;
				CHOIC(c_x+FILE_L,c_y,CHOIC_COLOR);
				C_9(); 
				C_16();
			}
		}
	}
	return c_y;
}

/*---------在第i行第j列用颜色color绘制单个数字方格-----------------------*/
Paint_L(int i,int j,int color)
{
	char *str;
	int x,y,d,t=1,p=0,q;
	x=WIN_X+j*WIN_LEN/n;  
	y=WIN_Y+FILE_H+i*WIN_LEN/n;
	setfillstyle(1,color);
	bar3d(x,y+5,x+WIN_LEN/n-5,y+WIN_LEN/n,5,5);
	sprintf(str,"%d",A[i][j]->data);
	outtextxy(x+WIN_LEN/n/2,y+WIN_LEN/n/2,str);
}

/*-----方格数字初始化-----------------------------*/
init_A()
{
	int i,j,x,y,d=0;
	int r,l;
	int p[LatticeAmount2];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{ 
			A[i][j]=(struct Lattice *)malloc(sizeof(struct Lattice));
			A[i][j]->row=i; 
			A[i][j]->line=j;
			A[i][j]->data=i*n+j;
		}
		while(d<exp)
		{
			for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					if(A[i][j]->data==0) 
					{ 
						X_0=i; 
						Y_0=j;
					}  
			randomize();
			i=random(4);  
			if(i==0)
			{ 
				r=X_0;  
				l=Y_0+1;
			}
			else 
			if(i==1)
			{ 
				r=X_0-1; 
				l=Y_0;
			}
			else 
			if(i==2)
			{ 
				r=X_0; 
				l=Y_0+1;
			}
			else 
			if(i==3)
			{ 
				r=X_0+1; 
				l=Y_0;
			}
			if(!IsBeyond(r,l))  
			{ 
				change_Num(&A[X_0][Y_0]->data,&A[r][l]->data);
				X_0=r;
				Y_0=l;  
				d++;
				x=WIN_X+WIN_LEN/2; 
				y=WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2;
				outtextxy(x-50,y-12,"Waiting...");
				rectangle(x-50,y-1,x+50,y+1);
				for(i=0;i<100/exp;i++)
				{ 
					line(x-50+i+(d-1)*100/exp,y-1,x-50+i+(d-1)*100/exp,y+1);
					delay(1000);                      
				}
			}
		}
		Clear_Dlg();
}

/*---------显示当前状态图--------------------------*/
view()
{ 
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			Paint_L(i,j,BK_COLOR);
}

/*------------找到当前状态的'0'位置-------------------*/
find_0(int *r,int *l)
{ 
	int i,j,x,y;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(A[i][j]->data==0)
			{ 
				*r=i; 
				*l=j;
			}  
	x=WIN_X+*l*WIN_LEN/n;  
	y=WIN_Y+FILE_H+*r*WIN_LEN/n;
	setfillstyle(1,S_COLOR);
	bar(x+1,y+1,x+WIN_LEN/n-1,y+WIN_LEN/n-1);
	outtextxy(x+WIN_LEN/n/2,y+WIN_LEN/n/2,"0");
	return;
}

/*----------获取当前状态，并赋给参数p---------------------*/
Obtain_State(struct CurState *p)
{ 
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++) 
		{ 
			p->state[i*n+j]=A[i][j]->data;
		}
}

/*----------将当前状态节点入栈----------------------------*/
InStack(struct CurState *p)
{ 
	int i;
	first++;   
	for(i=0;i<difficulty;i++)
		Stack[first].state[i]=p->state[i];
	Stack[first].rule=p->rule; 
	Stack[first].deep=p->deep; 
}

/*----------获取栈顶节点-----------------------------------*/
GetSF(struct CurState *p)
{ 
	int i;
	for(i=0;i<difficulty;i++)
		p->state[i]=Stack[first].state[i];
	p->rule=Stack[first].rule;
	p->deep=Stack[first].deep;
}

/*将栈顶节点（即当前状态）的数字赋给数组*A[N2][N2]，然后进行显示，并标记出空格*/
A_GetS(int deep)
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			A[i][j]->data=Stack[deep].state[i*n+j];
	view();
	find_0(&X_0,&Y_0);
}

/*----------判断是否为目标状态，是则返回1，否则返回0-------*/
int IsFS()
{ 
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(A[i][j]->data!=i*n+j) 
				return 0;
	return 1;
}

/*--------判断当前状态是否与栈内第i个节点状态相同----------*/
int IsBS_1(struct CurState *p,int i)
{  
	int k;
	for(k=0;k<difficulty;k++)
		if(p->state[k]!=Stack[i].state[k]) 
			return 0;
	return 1;
}

/*--------判断是否回到了以前某个状态，即是否与栈内任意某个节点状态相同-------*/
int IsBS(struct CurState *p)
{ 
	int i;
	for(i=first;i>=0;i--)
		if(IsBS_1(p,i)) 
			return 1;
	return 0;
}

/*-根据规则值决定移动方向。注意这里的x和y值是二维数组的下标值，而不是坐标值--*/
GetRule(struct CurState *p,int *x,int *y)
{ 
	if(p->rule==0)
	{ *x=X_0;  *y=Y_0-1;}
	else 
	if(p->rule==1)
	{ *x=X_0-1; *y=Y_0;}
	else
	if(p->rule==2)
	{ *x=X_0; *y=Y_0+1;}
	else 
	if(p->rule==3)
	{ *x=X_0+1; *y=Y_0;}
}

/*-------交换两个整数----------------------------------*/
change_Num(int *a,int *b)
{ 
	int i;
	i=*a; 
	*a=*b; 
	*b=i;
	return;
}

/*------交换空格'0'和另一相邻空格的操作-------------*/
Change(struct Lattice *p,struct Lattice *q)
{ 
	change_Num(&p->data,&q->data);
	Paint_L(p->row,p->line,BK_COLOR);
	find_0(&q->row,&q->line);
	p->next=q; 
	q->next=p;
	X_0=q->row;
	Y_0=q->line;
}

/*-----判断空恪'0'的相邻位置是否越界---------------*/
int IsBeyond(int i,int j)
{  
	if(i<0 || i>=n || j<0 || j>=n)
		return 1;
	return 0;
}

/*--------------寻找最优路径并显示-------------------------------*/
Show()
{  
	int x,y,i,j,k,wait=0;
	int d,t=1,p=0,q,step=0;
	char ch;
	char *str;

	result[Rp].deep=exp;
	infor=(struct CurState *)malloc(sizeof(struct CurState));
	Obtain_State(infor); 
	infor->rule=0; 
	infor->deep=0;
	InStack(infor);      

Repeat:
	while(!IsFS(infor))
	{
		if(kbhit())
		{
			ch=getch();
			if(ch==ESC) 
			{ 
				if(EXIT()) 
				{
					Clear_BG();
					return;
				}
			}; 
			if(ch==SPACE)  
				do
				{ 
					kbhit();
					ch=getch();
				}while(ch!=SPACE);
		}

		if(Stack[first].deep>result[Rp].deep)
		{   
			first-=2;
			Stack[first].rule++;
			A_GetS(first);
		}
		if(Stack[first].rule>3) 
		{
			first--;
			if(first==-1) 
				goto EXIT;  
			else
			{
				Stack[first].rule++;
				A_GetS(first);
			}
			GetSF(infor);
			continue;
		}
		GetSF(infor);
		GetRule(infor,&x,&y);   
		if(!IsBeyond(x,y))  
		{
			change_Num(&A[x][y]->data,&A[X_0][Y_0]->data);
			Obtain_State(infor);
			if(!IsBS(infor))
			{
				change_Num(&A[x][y]->data,&A[X_0][Y_0]->data);
				Change(A[X_0][Y_0],A[x][y]);
				step++;
				Obtain_State(infor);
				infor->rule=0;
				infor->deep++;
				InStack(infor); 
				x=WIN_X+WIN_LEN/2; 
				y=WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2;
				outtextxy(x-50,y-12,"Waiting...");
				rectangle(x-50,y-1,x+50,y+1);
				if(n==N1) 
					i=step%(exp+10);
				else 
				if(n==N2) 
					i=step%(exp*exp);
				if(i==0) 
					wait++;
				line(x-50,y,x-50+wait,y);
			}
			else
			{ 
				change_Num(&A[x][y]->data,&A[X_0][Y_0]->data);
				Obtain_State(infor);
				Stack[first].rule=++infor->rule;
			}
		}
		else  
			Stack[first].rule=++infor->rule;
	} /*---------------while()-----------------------------*/
	FLAG=1;
	if(result[Rp].deep>infor->deep)
	{  
		Clear_Dlg();
		outtextxy(WIN_X+WIN_LEN/2-50,WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2-10,
			"Find One Solution!");
		outtextxy(WIN_X+WIN_LEN/2-30,WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2+5,
			"Continue...");
		result[Rp].deep=infor->deep;
		sleep(2);
		Clear_Dlg();
	}
	for(i=0;i<=first;i++)
		result[Rp].S[i]=Stack[i];
	first-=2;
	Stack[first].rule++;
	A_GetS(first);
	goto Repeat;

EXIT:
	Clear_Dlg();
	if(FLAG)
	{ 
		Clear_Dlg();
		outtextxy(WIN_X+WIN_LEN/2-20,WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2-10,
			"Success!");
		outtextxy(WIN_X+WIN_LEN/2-130,WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2+5,
			"Press Enter to Show the Best Path!");
		while(1)
		{ 
			if(kbhit())
			{ 
				ch=getch();
				if(ch==Enter) 
				{ 
					Clear_Dlg();
					break;
				}   
				if(ch==ESC)
				{ 
					i=EXIT();
					if(i) 
					{ 
						Clear_BG();
						Clear_Dlg(); 
						return;
					}
				}
			}
		}
		for(j=0;j<=Rp;j++)
		{  
			for(i=0;i<=result[Rp].deep;i++)
			{ 
				if(kbhit())  
				{ 
					ch=getch();
					if(ch==ESC) 
						return;
					if(ch==SPACE)       
						do	          
						{ 
							kbhit();
							ch=getch();
						}while(ch!=SPACE);
				}
				Stack[i]=result[Rp].S[i];
				A_GetS(i);  
				sleep(1);
			}
		}
	}/*-------while(1)------*/
	Clear_Dlg();
	sprintf(str,"The depth of the Best Path is:  %d",result[Rp].deep);
	outtextxy(WIN_X+WIN_LEN/2-130,WIN_Y+FILE_H+WIN_LEN+Dlg_LEN/2,str);
}

main()
{ 
	int gdriver,gmode;
	char ch;
	detectgraph(&gdriver,&gmode);
	initgraph(&gdriver,&gmode,"c:\tc\tc");
	setbkcolor(0);
	clearviewport();
	F_SHOW();
}
上一页 12
💿 文件大小 126 K
👤 上传用户 pangyi
📂 所属分类书籍源码
🏷️ 相关标签

#书籍 #程序员 #代码
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -