CPP.rar_n*m的 c++华容道_华容道_华容道c++

#include <iostream.h> #include <fstream.h> int mark[]; //右来保存走法的 int num[2][2];//棋盘 int temp; int k ; int q ; string strAim = "123804765" //目标字符串，空格用0表示 string States[100];//字符窜数组 int iQuick; //有来退出递归的标志，1，表示找到走法，可以退出，0，怎么没有找到走法，继续走 Hrd(int i,int j)//华龙道算法，好像能找到结果，但是不能找到最少步数的结果，我不确定会不会还有漏洞。结果保存在mark[]中 { string str1; if (i!=0) //如果可以向上走，则向上走一步 { temp=num[i-1][j]; num[i-1][j]=num[i][j]; num[i][j]=temp ; //交换空格和它上面的数字 // 保存交换后的状态 str1=Change2Str(num[][]); //转化成字符串，用来比较 if (CompState(str1)) //比较变换后的状态是否在以前的状态中出现过 { //如果以前出现过，则返回 temp=num[i-1][j]; num[i-1][j]=num[i][j]; num[i][j]=temp ; // 把原来交换过的数字再交换过来 return ; } else//比较后，发现目前的状态以前没有出现过 { mark[k++]=1 ; if(strcmp(&strAim,& str1)=1)//跟目标比，看是否相等 { iquick=1; return; } else //不相等，没有达到最后我们的要求 { //1 代表向上走了一步 Add2States(str1); //保存现在的状态到状态数组中 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; // 保存交换后的状态 str1=Change2Str(num[][]); //转化成字符串，用来比较 if (CompState(str1)) //比较变换后的状态是否在以前的状态中出现过 { //如果以前出现过，返回 temp=num[i][j+1]; num[i][j+1]=num[i][j] ; num[i][j]=temp; // 把原来交换过的数字再交换过来 return; } else//比较后，发现目前的状态以前没有出现过 { mark[k++]=2 ; //2 代表向右走了一步 if(strcmp(&strAim,& str1)=1)//跟目标比，看是否相等 { iquick=1; return; } else //没有达到结果 { Add2States(str1); //保存现在的状态到状态数组中 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; // 保存交换后的状态 str1=Change2Str(num[][]); //转化成字符串，用来比较 if (CompState(str1)) //比较变换后的状态是否在以前的状态中出现过 { //如果以前出现过，则返回 temp=num[i+1][j]; num[i+1][j]=num[i][j]; num[i][j]=temp; // 把原来交换过的数字再交换过来 return ; } else//比较后，发现目前的状态以前没有出现过 { mark[k++]=3 ; //3 代表向下走了一步 if(strcmp(&strAim,& str1)=1)//跟目标比，看是否相等 { iquick=1; return; } else //没有达到最后我们的要求 { Add2States(str1); //保存现在的状态到状态数组中 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; // 保存交换后的状态 str1=Change2Str(num[][]); //转化成字符串，用来比较 if (CompState(str1)) //比较变换后的状态是否在以前的状态中出现过 { //如果以前出现过，则回溯 temp=num[i][j-1]; num[i][j-1]=num[i][j]; num[i][j]=temp; // 把原来交换过的数字再交换过来 return ; } else//比较后，发现目前的状态以前没有出现过 { mark[k++]=4 ; //1 代表向右走了一步 if(strcmp(&strAim,& str1)=1)//跟目标比，看是否相等 { iquick=1; return; } else //没有达到最后我们的要求 { Add2States(str1); //保存现在的状态到状态数组中 Hrd(i,j-1) ; //递归，继续遍历 if (iquick=1) { return; } } } } //如果都走过了，则返回 k--; 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; } Add2States(string str1) { States[q++]=str1 ; } main() { num[0][0]=1; num[0][1]=2; num[0][2]=3; num[1][0]=8; num[1][1]=6; num[1][2]=4; num[2][0]=1; num[2][1]=0; num[2][2]=5; hrd(2,1); for(int i=0 ,i<100,i++) {count<<mark[i]<<endl; } }