int mark[] //右来保存走法的
int num[][]//棋盘
int temp
int k
string strAim
strAim="123804765"//目标字符串,空格用0表示
string States[]//字符窜数组
int iQuick //有来退出递归的标志,1,表示找到走法,可以退出,0,怎么没有找到走法,继续走
Hrd(int i,int j)//华龙道算法,好像能找到结果,但是不能找到最少步数的结果,我不确定会不会还有漏洞。结果保存在mark[]中
{
if (i!=0) //如果可以向上走,则向上走一步
{
temp=num[i-1][j]
num[i-1][j]=num[i][j]
num[i][j]=temp //交换空格和它上面的数字
// 保存交换后的状态
str=Change2Str(num[][]) //转化成字符串,用来比较
if (CompState(str)) //比较变换后的状态是否在以前的状态中出现过
{
//如果以前出现过,则返回
temp=num[i-1][j]
num[i-1][j]=num[i][j]
num[i][j]=temp // 把原来交换过的数字再交换过来
return
}
else//比较后,发现目前的状态以前没有出现过
{
if(strcmp(&strAim,& str)=1)//跟目标比,看是否相等
{
iquick=1
return
}
else //不相等,没有达到最后我们的要求
{
mark[k++]=1 //1 代表向上走了一步
Add2States(str) //保存现在的状态到状态数组中
Hrd(i-1,j)
if (iquick=1) //可以退出
{
return
}
} //递归,继续遍历
}
}
if(j!=2)//如果可以向右走,则向右走一步
{
temp=num[i][j+1]
num[i][j+1]=num[i][j]
num[i][j]=temp
// 保存交换后的状态
str=Change2Str(num[][]) //转化成字符串,用来比较
if (CompState(str)) //比较变换后的状态是否在以前的状态中出现过
{
//如果以前出现过,返回
temp=num[i][j+1]
num[i][j+1]=num[i][j]
num[i][j]=temp // 把原来交换过的数字再交换过来
return
}
else//比较后,发现目前的状态以前没有出现过
{
if(strcmp(&strAim,& str)=1)//跟目标比,看是否相等
{
iquick=1
return
}
else //没有达到结果
{
mark[k++]=2 //2 代表向右走了一步
Add2States(str) //保存现在的状态到状态数组中
Hrd(i,j+1) //递归,继续遍历
if (iquick=1)
{
return
}
}
}
}
if (i!=2)// 如果可以向下走,则向下走一步
{
temp=num[i+1][j]
num[i+1][j]=num[i][j]
num[i][j]=temp
// 保存交换后的状态
str=Change2Str(num[][]) //转化成字符串,用来比较
if (CompState(str)) //比较变换后的状态是否在以前的状态中出现过
{
//如果以前出现过,则返回
temp=num[i+1][j]
num[i+1][j]=num[i][j]
num[i][j]=temp // 把原来交换过的数字再交换过来
return
}
else//比较后,发现目前的状态以前没有出现过
{
if(strcmp(&strAim,& str)=1)//跟目标比,看是否相等
{
iquick=1
return
}
else //没有达到最后我们的要求
{
mark[k++]=3 //3 代表向下走了一步
Add2States(str) //保存现在的状态到状态数组中
Hrd(i+1,j) //递归,继续遍历
if (iquick=1)
{
return
}
}
}
}
if (j!=0)//如果可以向左走,则向左走一步
{
temp=num[i1][j-1]
num[i][j-1]=num[i][j]
num[i][j]=temp
// 保存交换后的状态
str=Change2Str(num[][]) //转化成字符串,用来比较
if (CompState(str)) //比较变换后的状态是否在以前的状态中出现过
{
//如果以前出现过,则回溯
temp=num[i][j-1]
num[i][j-1]=num[i][j]
num[i][j]=temp // 把原来交换过的数字再交换过来
k=k-1 //如果都遍历过了则回朔,这步很重要
return
}
else//比较后,发现目前的状态以前没有出现过
{
if(strcmp(&strAim,& str)=1)//跟目标比,看是否相等
{
iquick=1
return
}
else //没有达到最后我们的要求
{ mark[k++]=4 //1 代表向右走了一步
Add2States(str) //保存现在的状态到状态数组中
Hrd(i,j-1) //递归,继续遍历
if (iquick=1)
{
return
}
}
}
}
}
void Change2Str(int arr[][])// 把二维数组转换成一个字符串
{int i,j
string strState
for (i=0;i<3 ;i++ )
{for (j=0;j<3 ;j++ )
{
strState= strState & arr[i][j]
}
}
return strState
}
void CompState(string str1 )//比较当前的状态是否再以前的状态中出现过
{ int i
for (i=0;i<len(states[])-1 ; i++)//len(states[]),取得数组的长度,有点忘了
{
if (strcmp(&States[i],&str1)!=0)//如果两个字符串相等,则函数返回true
{
return true
}
}
return false
}