十五数码问题
做完八数码之后我还想做难一点的东西，因为八数码直接爆搜就可以了，所以想做一下爆搜不能做的东西，十五数码如果爆搜的话有15！种状态，不可能存下的；
我的思路是不存那么多状态，我把所有的状态hash到10000大小的vector数组里面，每次搜索不可能吧所有的状态都遍历完，所以不会爆内存的，然后存路径是用
链表做的，将后面扩展到的状态指向前一个状态，在搜索到的时候就从最后一个向前遍历，然后把方向存在一个栈中，输出就可以了
下面粘代码：
#include <iostream>#include <cstring>#include <queue>#include <stack>#include <cmath>#include <vector>using namespace std ;struct Node { int h , step ; long long key ; char dir ; Node * pre ;} ;struct cmp { bool operator () ( Node a , Node b ) { return a.h < b.h ; }} ;long long fac[17] ;vector < long long > Hash[10000] ;Node *END ;void init() ;long long cantor( int s[] ) ;void uncantor( int s[] , long long num ) ;int h( int s[] ) ;bool AStar( int s[] ) ;bool check( long long ) ;int main(){ int str[16] ; char ch ; init() ; memset( Hash , 0 , sizeof( Hash ) ) ; for( int i = 0 ; i <= 15 ; i ++ ) { cin >> ch ; if( ch == 'x' ) str[i] = 16 ; else if( ch >= '0' && ch <= '9' ) str[i] = ch - '0' ; else str[i] = 10 + ch - 'A' ; } if( AStar( str ) ) { stack < char > s ; while( END->pre != NULL ) { s.push( END->dir ) ; END = END->pre ; } while( !s.empty() ) { cout << s.top() ; s.pop() ; } cout << endl ; } else cout << "unsolvable" << endl ; return 0 ;}void init(){fac[0] = 1 ;for( int i = 1 ; i <= 16 ; i ++ )fac[i] = i * fac[i-1] ;}long long cantor( int s[] ){ long long num = 0 , t ; for( int i = 0 ; i < 16 ; i ++ ) { t = 0 ; for( int j = i + 1 ; j < 16 ; j ++ ) if( s[i] > s[j] ) t ++ ; num += fac[16 - i - 1] * t ; } return num ;}void uncantor( int s[] , long long num ){long long j , t , r ;bool p[17] ;memset( p , 0 , sizeof( p ) ) ;for( int i = 0 ; i < 16 ; i ++ ){t = num / fac[16 - i - 1] + 1 ;num %= fac[16 - i - 1] ;r = 0 , j = 1 ;while( 1 ){if( !p[j] ) r ++ ;if( r == t ) break ;j ++ ;}s[i] = j ; p[j] = 1 ;}}int h( int s[] ){ int H = 0 ; for( int i = 0 ; i < 16 ; i ++ ) if( s[i] != 16 && i == s[i] - 1 ) H ++ ; return H ;}bool check( long long num ){ int key = num % 10000 ; bool flag = 0 ; for( int i = 0 ; i < Hash[key].size() ; i ++ ) if( Hash[key][i] == num ) { flag = 1 ; break ; } return ( 1 - flag ) ;}bool AStar( int s[] ){ int str[16] , flag = 0 , i ; long long t ; priority_queue< Node , vector< Node > , cmp > q ; Node * start = new Node ; start->key = cantor( s ) ; start->pre = NULL ; start->h = h( s ) ; start->step = 0 ; start->dir = '0' ; int num = start->key % 10000 ; Hash[num].push_back( start->key ) ; q.push( *start ) ; while( !q.empty() ) { Node * temp = new Node ; * temp = q.top() ; q.pop() ; if( temp->key == 0 ){ flag = 1 ; END = temp ; break ; } uncantor( str , temp->key ) ; for( i = 0 ; i < 16 ; i ++ ) if( str[i] == 16 ) break ; if( i != 0 && i != 1 && i != 2 && i != 3 ) { swap( str[i] , str[i-4] ) ; t = cantor( str ) ; if( check( t ) ) { Node *tmp = new Node ; tmp->dir = 'u' ; tmp->h = h( str ) ; tmp->key = t ; tmp->pre = temp ; tmp->step = temp->step + 1 ; num = t % 10000 ; Hash[num].push_back( t ) ; q.push( *tmp ) ; } swap( str[i] , str[i-4] ) ; } if( i != 12 && i != 13 && i != 14 && i != 15 ) { swap( str[i] , str[i+4] ) ; t = cantor( str ) ; if( check( t ) ) { Node *tmp = new Node ; tmp->dir = 'd' ; tmp->h = h( str ) ; tmp->key = t ; tmp->pre = temp ; tmp->step = temp->step + 1 ; num = t % 10000 ; Hash[num].push_back( t ) ; q.push( *tmp ) ; } swap( str[i] , str[i+4] ) ; } if( i != 0 && i != 4 && i != 8 && i != 12 ) { swap( str[i] , str[i-1] ) ; t = cantor( str ) ; if( check( t ) ) { Node *tmp = new Node ; tmp->dir = 'l' ; tmp->h = h( str ) ; tmp->key = t ; tmp->pre = temp ; tmp->step = temp->step + 1 ; num = t % 10000 ; Hash[num].push_back( t ) ; q.push( *tmp ) ; } swap( str[i] , str[i-1] ) ; } if( i != 3 && i != 7 && i != 11 && i != 15 ) { swap( str[i] , str[i+1] ) ; t = cantor( str ) ; if( check( t ) ) { Node *tmp = new Node ; tmp->dir = 'r' ; tmp->h = h( str ) ; tmp->key = t ; tmp->pre = temp ; tmp->step = temp->step + 1 ; num = t % 10000 ; Hash[num].push_back( t ) ; q.push( *tmp ) ; } swap( str[i] , str[i+1] ) ; } } return flag ;}