华容道游戏是非常经典的BFS应用的题目。
下面是几个我参考过的链接：
使用java语言实现，充分体现OOAD和数据结构的应用，讲的非常详细，但是太过于复杂了：
http://www.cppblog.com/tx7do/archive/2006/09/18/12691.html
简单版本的介绍，非常有用，而且有完整的源代码：
http://blog.chinaunix.net/u/19651/showart_395172.html
虽然讲的详细，但是代码也成这副样子，值得同情：
http://www.fjptsz.com/xxjs/xjw/rj/110.htm
下面是我通过这道题的一些体会：
1、重复状态的判重方法
在很多与走步有关的题目中，一般会涉及到重复状态的检测，在搜索过程中需要忽略掉这些重复状态，这样才能避免不必要的搜索代价。
我使用通过对局面做hash的方法来检测是否存在重复状态，只有不重复的新状态才插入到hash表中。原来hash函数是通过对grid[5][4]这个局面进行移位运算来产生分布均匀的hash值，但是效果始终不理想。
int getHashValue(char grid[5][4]) {
int mask13=0x0001fff; //低位连续的13个1
int mask19=0x007ffff; //低位连续的19个1
int result=0,tmp;
for(int i=0;i<5;i=i+2){
tmp=(grid[i][0]<<24) | (grid[i][1]<<16) | (grid[i][2]<<8) | (grid[i][3]);
result += (((tmp & (mask13<<13))>>13) | ((tmp & mask19)<<19));
result ^=(grid[i+1][0]<<24) | (grid[i+1][1]<<16) | (grid[i+1][2]<<8) | (grid[i+1][3]);
}
result= (result<=0)? -result: result;
return result%HashTableSize; //最后一定要对HashTable取余
}
后来我发现可以将局面转化为字符串的形式，然后对字符串进行hash处理，这样得到的hash函数效果非常好，因为本身对string就有一个很好的hash函数。
int getHashValue(char grid[5][4]) {
char* grid_begin= &grid[0][0];
char* grid_end= &grid[5][0];
string str(grid_begin , grid_end) ;
int result=0 ;
for( int i=0 ; i<str.length() ; i++)
result = 37* result + str[i];
result = result % HashTableSize ;
if( result <0 )
result += HashTableSize ;
return result ;
}
注意string类型hash函数的写法，如果在取余操作后，result的值小于0，那么还要加上HashTableSize的值。
通过这个hash函数：
1、C++中如何将字符数组转化为字符串呢？
利用string类的构造函数
string类的主要几个构造函数为：
string(); string( size_type length, char ch ); string( const char *str ); string( const char *str, size_type length ); string( string &str, size_type index, size_type length ); string( input_iterator start, input_iterator end );
下面我给出几个测试例子：
#include<iostream>
#include<string>
using namespace std;
int main(){
char init_grid[5][4]={
'v','c','0','v',/
'0','0','0','0',/
'v','h','0','v',/
'0','s','s','0',/
's','b','b','s'
};
char* grid_begin=&init_grid[0][0]; //通过首末指针来调用构造函数
char* grid_end = &init_grid[5][0];
string str(grid_begin,grid_end);
cout<<str<<endl;
char a[5]={
'h','e','e','o','p'
};
//调用string的构造函数：string( const char *str );
string str1(a,a+5); //对于一维数组可以使用指针的思想
cout<<str1<<endl;
const char* b="hello"; //直接使用const char*参数调用构造函数
string str2(b);
cout<<str2<<endl;
return 0;
}
可以看到这巧妙的使用第四个构造函数：string( input_iterator start, input_iterator end )
对于C++中的内置类型数据迭代器对应的其实就是指针，在这个例子中grid二维数组的末指针可以为 &grid[4][5]，也可以是grid[5][0].
这里如果直接使用string的第二构造函数 string( const char *str ); 并以 &grid[0][0]作为参数，获得的string对象中是有乱码的。
2、保证hash表的大小为素数
当hash表的大小为素数时，可以减少冲突的发生可能性。下面是一个获取某个数的下一个素数的测试程序：
#include<iostream>
#include<cstdio>
#include<fstream>
using namespace std;
bool isPrime(unsigned int a){
if( a==2 || a == 3)
return true ;
if( a==1 || a%2 == 0 )
return false ;
for(int i=3 ; i*i<=a ; i+=2){
if( a % i == 0)
return false ;
}
return true ;
}
int nextPrime(unsigned int a){
if( a % 2 == 0)
a++;
for( ; !isPrime(a) ; a+=2) ;
return a ;
}
int main(int argc,char* argv[]) {
cout<<nextPrime(1<<18)<<endl;
return 0;
}
转载文章出处：http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5850715