广度搜索.cpp

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一

#include<stdio.h>
#include<conio.h>
int n;// open结构的指针
int w=0;
char start[10];
char end[9]={'1','2','3','8','0','4','7','6','5'};//目标节点
typedef struct ma
{ char shuma[9];
 char operation;
 int father;
}ma;
ma base[4000];

void match(int n7)//比较函数，输出结果
{int n6=0;
int n8,n9;
int result[60];
while(n6<9)
{if(base[n7].shuma[n6]!=end[n6])
 return;
 n6++;
}
n8=n7;n9=0;
while(base[n8].father!=-1)
{result[n9]=base[n8].father;
 n8=base[n8].father;
 n9++;
 }
n9--;
while(n9>=0)
{n8=result[n9];
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n8].shuma[0],base[n8].shuma[1],base[n8].shuma[2]);
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n8].shuma[3],base[n8].shuma[4],base[n8].shuma[5]);
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n8].shuma[6],base[n8].shuma[7],base[n8].shuma[8]);
printf("\n\n\n");
n9--;}
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n7].shuma[0],base[n7].shuma[1],base[n7].shuma[2]);
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n7].shuma[3],base[n7].shuma[4],base[n7].shuma[5]);
printf("\n\t\t%c\t\t%c\t\t%c\n",base[n7].shuma[6],base[n7].shuma[7],base[n7].shuma[8]);
printf("\n\n\n");
w++;
}

void left(int n2)
{int n3,n4;//n3 代表0的位置
n3=0;
while(base[n2].shuma[n3]!='0')
{n3++;}
if(n3==0||n3==3||n3==6)
{return;}
for(n4=0;n4<9;n4++)
{base[n].shuma[n4]=base[n2].shuma[n4];}
base[n].shuma[n3]=base[n].shuma[n3-1];
base[n].shuma[n3-1]='0';
base[n].father=n2;
base[n].operation='L';
match(n);
n++;
}

void right(int n2)
{int n3,n4;//n3 代表0的位置
n3=0;
while(base[n2].shuma[n3]!='0')
{n3++;}
if(n3==2||n3==5||n3==8)
{return;}
for(n4=0;n4<9;n4++)
{base[n].shuma[n4]=base[n2].shuma[n4];}
base[n].shuma[n3]=base[n].shuma[n3+1];
base[n].shuma[n3+1]='0';
base[n].father=n2;
base[n].operation='R';
match(n);
n++;
}
void up(int n2)
{int n3,n4;//n3 代表0的位置
n3=0;

while(base[n2].shuma[n3]!='0')
{n3++;}
if(n3==0||n3==1||n3==2)
{return;}
for(n4=0;n4<9;n4++)
{base[n].shuma[n4]=base[n2].shuma[n4];}
base[n].shuma[n3]=base[n].shuma[n3-3];
base[n].shuma[n3-3]='0';
base[n].father=n2;
base[n].operation='U';
match(n);
n++;
}
void down(int n2)
{int n3,n4;//n3 代表0的位置
n3=0;
while(base[n2].shuma[n3]!='0')
{n3++;}
if(n3==6||n3==7||n3==8)
{return;}
for(n4=0;n4<9;n4++)
{base[n].shuma[n4]=base[n2].shuma[n4];}
base[n].shuma[n3]=base[n].shuma[n3+3];
base[n].shuma[n3+3]='0';
base[n].father=n2;
base[n].operation='D';
match(n);
n++;
}

void main()
{n=2;
int n9=0;
int num=0;
printf("输入字符串，以0代表空格格式如：283164705+回车:\n");
scanf("%s",start);
if(start[0]==end[0]&&start[1]==end[1]&&start[2]==end[2]&&start[3]==end[3]&&start[4]==end[4]&&start[5]==end[5]&&start[6]==end[6]&&start[7]==end[7]&&start[8]==end[8])
{printf("输入的数码就是所求数码\n");
 return;}
for(int n1=0;n1<9;n1++)//设置初始值
{base[1].shuma[n1]=start[n1];}
base[1].operation='N';
base[1].father=-1;
for(n1=1;n<4000;n1++)
{
if(base[n1].operation=='L')
{  left(n1);
if(w)
return;
 up(n1);
 if(w)
return;
 down(n1);
if(w)
return;}
 
if(base[n1].operation=='R')
{ right(n1);
if(w)
return;
up(n1);
if(w)
return;
down(n1);
if(w)
return;}

if(base[n1].operation=='U')
 {up(n1);
if(w)
return;
right(n1);
if(w)
return;
left(n1);
if(w)
return;}
 
if(base[n1].operation=='D')
 {left(n1);
if(w)
return;
right(n1);
if(w)
return;
down(n1);
if(w)
return;}

if(base[n1].operation=='N')
 {right(n1);
if(w)
return;
up(n1);
if(w)
return;
down(n1);
if(w)
return;
left(n1);
if(w)
return;}
}
printf("\n在规定长度内，不能实现8数码问题\n");
}