#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 100
typedef struct Node//状态结点
{
int data[2][2]; //状态结点数组
struct Node *parent; //指向状态结点的父结点指针
int deep;//有界深度
}SNode;
typedef struct//List 顺序栈
{
SNode *data[MaxSize]; //状态结点地址数组
int top;
int n; //待扩展/已扩展状态结点序号(选)
}Stack;
void Initstack(Stack *&St)//初始栈
{
St=(Stack *)malloc(sizeof(Stack));
St->top=-1;
}
int Enststack(Stack *&St,SNode *S)//进栈 Close表不用出栈
{
if(St->top==MaxSize-1)
return 0;
else
{
St->top++;
St->data[St->top]=S;
St->n++;
return 1;
}
}
int Deststack(Stack *&St,SNode *&S)//出栈
{
if(St->top==-1)
return 0;
S=St->data[St->top];
St->top--;
return 1;
}
int Emptystack(Stack *St)//栈空判断
{
if(St->top==-1)
return 1;
return 0;
}
int JudgeGoalS(SNode *So,SNode *Sg)//判断目标状态
{
int i,j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(So->data[i][j] != Sg->data[i][j])
return 0;
}
}
return 1;
}
//判断新生成的状态结点是否在搜索图中出现过
int Checkopenlist(Stack *Open, int data[2][2])//检查 OPENList
{
if(Emptystack(Open))
return 0;
int i,j,m;
for(m=0;m<=Open->top;m++)
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(data[i][j] != Open->data[m]->data[i][j])
i=2;
if(i==1 && j==1)
return 1;
}
}
return 0;
}
int Checkclosedlist(Stack *Close, int data[2][2])//检查 ClosedList
{
if(Emptystack(Close))
return 0;
int i,j,m;
for(m=0;m<=Close->top;m++)
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(data[i][j] != Close->data[m]->data[i][j])
i=2;
if(i==1 && j==1)
return 1;
}
}
return 0;
}
//扩展结点
int JudgeOPostion(SNode *So)//判断待扩展结点的空格位置
{
int i,j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
if(So->data[i][j]==0)
{
if(i==0 && j==0)
return 1;
else if(i==0 && j==1)
return 2;
else if(i==1 && j==0)
return 3;
else if(i==1 && j==1)
return 4;
}
}
}
return 0;
}
void developSnode(SNode *&S, SNode *So, int c, int n, int temp)//扩展结点
{
switch(c)
{
case 1:if(n==2)//向下
{
S->data[0][0]=So->data[1][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[0][0]; S->data[1][1]=So->data[1][1];
}
else if(n==1)//向右
{
S->data[0][0]=So->data[0][1]; S->data[0][1]=So->data[0][0];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[1][1];
}
break; //i=0;j=0;
case 2:if(n==2)//向左
{
S->data[0][0]=So->data[0][1]; S->data[0][1]=So->data[0][0];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[1][1];
}
else if(n==1)//向下
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[1][1];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[0][1];
}
break; //i=0;j=1;
case 3:if(n==2)//向右
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[1][1]; S->data[1][1]=So->data[1][0];
}
else if(n==1)//向上
{
S->data[0][0]=So->data[1][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[0][0]; S->data[1][1]=So->data[1][1];
}
break; //i=1;j=0;
default:if(n==2)//向上
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[1][1];
S->data[1][0]=So->data[1][0]; S->data[1][1]=So->data[0][1];
}
else if(n==1)//向左
{
S->data[0][0]=So->data[0][0]; S->data[0][1]=So->data[0][1];
S->data[1][0]=So->data[1][1]; S->data[1][1]=So->data[1][0];
}
break; //i=1,j=1;
}
}
/*注：
switch (c):
c=1,2,3,4(default) 对应结点空格的四个位置，以确定如何生成子结点。
case 1: //i=0;j=0;
case 2: //i=0;j=1;
case 3: //i=1;j=0;
default: //i=1,j=1;
扩展结点 So，新生成结点 S
n:每个结点最多生成 2 个子结点
n=2 新生成结点 S,入队
n=1 新生成结点 S,入队
temp 表示空格,在此以0表示空格
*/
void Print_Solution(SNode *S)//打印节点
{
int i,j;
printf("\n");
while(S != NULL)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",S->data[i][j]);
if(j==1)
printf("\n");
}
if(S->parent!=NULL)
{
printf(" ^\n");
printf(" |\n");
}
S=S->parent;
}
printf("\n");
}
void Print_Open(SNode *S)
{
int i,j;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",S->data[i][j]);
if(j==1)
printf("\n");
}
printf("\n");
}
void Print_Close(Stack *St)
{
int i,j,k;
printf("Close List:\n");
for(k=0;k<=St->top;k++)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
printf("%d ",St->data[k]->data[i][j]);
if(j==1)
printf("\n");
}
printf("\n");
}
}
void main()
{
SNode *Sn,*S,*So,*Sg;
Stack *Open,*Close;
int j,i,n=2,c;//n is number of developed subnodes //,top
int dataso[2][2]={3,1,
0,2},
datasg[2][2]={1,2,
0,3};
//int dataso[2][2]={0,1,3,2},datasg[2][2]={1,2,0,3};
int dm=3;
So=(SNode *)malloc(sizeof(SNode));
Sg=(SNode *)malloc(sizeof(SNode));
So->parent=NULL;
So->deep=0;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
So->data[i][j]=dataso[i][j];
Sg->data[i][j]=datasg[i][j];
}
}
Initstack(Open);
Initstack(Close);
printf("Open List:\n");
Enststack(Open,So);//进栈
Print_Open(So);
while(Emptystack(Open) !=1 ) // Search States Space Graph
{
Deststack(Open,S);//取出open表第一个节点
Enststack(Close,S);//放入close表
if(S->deep==dm)
{
continue;//标记节点n为待扩展节点
}
So=S; // Saved Parent
if (JudgeGoalS(So,Sg)==1)
{
Print_Close(Close);
printf("Find solution!\n");
Print_Solution(So);
dm=Sg->deep;
break;
}
else
{
c=JudgeOPostion(So);//int JugeOPostion(Snoed *So);
while(n>=1)
{
Sn=(SNode *)malloc(sizeof(SNode)); // Sn New Generating Node
developSnode(Sn,So,c,n,0); // Sn->Parent=So, c: So空格位置, n: Possible New Node Number, 0:空格取值
if((Checkopenlist(Open,Sn->data) !=1) && (Checkclosedlist(Close,Sn->data) !=1)) // Check whether Sn in OPEN＋CLOSED
{
Sn->parent=So;// Sn Parent
Sn->deep=So->deep+1;// Sn->deep=So->deep+1;
Enststack(Open,Sn);// Sn Enter Stack
Print_Open(Sn);
}
n--; // Next Child Node of So
} //Generating two children Nodes SnS of So
n=2; // when develop Next So，reset number of sub-nodes of So
}
}
if (Emptystack(Open)==1)
{
printf("No solution!\n");
printf("\n");
Print_Close(Close);
}
}
