|
Posted on 2010-08-21 19:47 Kevin_Zhang 阅读(260) 评论(0) 编辑 收藏 引用 所属分类: 搜索
转载自 http://hi.baidu.com/happynp/blog/item/06820fcaf41d4683c817681c.html
Tag:BFS+Hashtable
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const unsigned int M = 490001;
#define NIL -1
#define SWAP(x,y) (x)^=(y)^=(x)^=(y)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dir[4][2] = {
1, 0, // D
-1, 0, // U
0,-1, // L
0, 1 // R
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int revDir[4] = { 1, 0, 3, 2 };
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) char dirStr[] = {"dulr"};
char solution[M];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) typedef struct Node {
int v; // 状态原值
int r; // 到下一状态值的变化方向
}Node;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Node Hash_s[M], Hash_e[M];
Node Q_s[M], Q_e[M];
int Qs_h, Qs_t, Qe_h, Qe_t;
Node ns, ne;
int cnt[100];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline int hashcode(int v)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
return v % M;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool Insert(Node hash[], const Node &nod)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int key = hashcode(nod.v);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( hash[key].v == 0 ) {
hash[key] = nod;
return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else {
if(hash[key].v == nod.v)
return false;
while( hash[ hashcode(++key) ].v ) ;
hash[ hashcode(key)] = nod;
return true;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Node * Query(Node hash[], const Node &nod)
// false / true : Not / Yes exist in the hash table
// if Yes, theNod return the existed Node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int key = hashcode(nod.v);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( hash[key].v == 0 ) {
return NULL;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) else {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(hash[key].v == nod.v) {
return &hash[key];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while( hash[ hashcode(++key) ].v ) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( hash[ hashcode(key)].v == nod.v ) {
return &hash[key];
}
}
return NULL;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int ToArry(int v, int (*p)[3])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i, pos;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=8; i>=0; i--) {
p[ i / 3 ][ i % 3 ] = v % 10;
v /= 10;
if( p[ i / 3 ][ i % 3 ] == 0 )
pos = i;
}
return pos; // 'x' 的位置
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int ToValue(int (*p)[3])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int v = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0; i<=8; i++) {
v = v * 10 + p[ i / 3 ][ i % 3 ];
}
return v;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void GetOptimPath(int arr[], Node hash[], Node curNod, bool starToEnd, int &nIndex)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
Node *pNod;
int curArr[3][3];
for( ; curNod.r != NIL; )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
arr[nIndex++] = starToEnd ? curNod.r : revDir[curNod.r];
const int loca = ToArry(curNod.v, curArr);
int row = loca / 3;
int col = loca % 3;
int nxtrow = row + dir[revDir[curNod.r]][0];
int nxtcol = col + dir[revDir[curNod.r]][1];
SWAP(curArr[row][col], curArr[nxtrow][nxtcol]);
int nxtv = ToValue(curArr);
curNod.v = nxtv;
pNod = Query(hash, curNod);
curNod.r = pNod->r;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
Qs_h = Qs_t = 0;
Qe_h = Qe_t = 0;
Q_s[Qs_t++] = ns;
Q_e[Qe_t++] = ne;
Insert(Hash_s, ns);
Insert(Hash_e, ne);
int nIndex = 0;
int now;
Node curNod, nxtNod;
int curArr[3][3], nxtArr[3][3];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(1) {
if( ( Qs_h == Qs_t || Qe_h == Qe_t ) )
break;
now = Qs_t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while( Qs_h < now ) {
curNod = Q_s[Qs_h++];
const int loca = ToArry(curNod.v, curArr);
int row = loca / 3;
int col = loca % 3;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0; i<4; i++) {
memcpy(nxtArr, curArr, sizeof(curArr));
int nxtrow = row + dir[i][0];
int nxtcol = col + dir[i][1];
if( !( nxtrow >= 0 && nxtrow < 3 && nxtcol >= 0 && nxtcol < 3 ) ) continue;
SWAP(nxtArr[row][col], nxtArr[nxtrow][nxtcol]);
int nxtv = ToValue(nxtArr);
nxtNod.v = nxtv;
nxtNod.r = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Query( Hash_e, nxtNod) != NULL ) { // find the solution
Node commNod(nxtNod);
GetOptimPath(cnt, Hash_s, commNod, true, nIndex);
for( int i=0; i < nIndex / 2; i++ )
SWAP(cnt[i], cnt[nIndex-1-i]);
commNod = *Query(Hash_e, nxtNod);
GetOptimPath(cnt, Hash_e, commNod, false, nIndex);
goto Solved;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Insert( Hash_s, nxtNod) ) {
Q_s[Qs_t++] = nxtNod;
}
}
}
now = Qe_t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while( Qe_h < now ) {
curNod = Q_e[Qe_h++];
const int loca = ToArry(curNod.v, curArr);
int row = loca / 3;
int col = loca % 3;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0; i<4; i++) {
memcpy(nxtArr, curArr, sizeof(curArr));
int nxtrow = row + dir[i][0];
int nxtcol = col + dir[i][1];
if( !( nxtrow >= 0 && nxtrow < 3 && nxtcol >= 0 && nxtcol < 3 ) ) continue;
SWAP(nxtArr[row][col], nxtArr[nxtrow][nxtcol]);
int nxtv = ToValue(nxtArr);
nxtNod.v = nxtv;
nxtNod.r = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Query( Hash_s, nxtNod) != NULL ) {
Node commNod(nxtNod);
GetOptimPath(cnt, Hash_e, commNod, false, nIndex);
for( int i = 0; i < nIndex / 2; i++ )
SWAP(cnt[i], cnt[nIndex-1-i]);
commNod = *Query(Hash_s, nxtNod);
GetOptimPath(cnt, Hash_s, commNod, true, nIndex);
for( i = 0; i < nIndex / 2; i++ )
SWAP(cnt[i], cnt[nIndex-1-i]);
goto Solved;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if( Insert( Hash_e, nxtNod) ) {
Q_e[Qe_t++] = nxtNod;
}
}
}
}
Solved:
int i=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=0; i<nIndex; i++) {
solution[i] = dirStr[cnt[i]];
}
solution[i] = '\0';
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Input()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
char ch;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) int i = 0, arr[3][3] = { 1,2,3,4,5,6,7,8,0 };
ne.v = ToValue(arr);
ne.r = NIL;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i=0; i < 9; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) do {
scanf("%c", &ch);
}
while( !( ( ch >= '1' && ch <= '8' ) || ( ch == 'x' ) ) ) ;
if( ch == 'x' )
arr[ i / 3 ][ i % 3 ] = 0;
else
arr[ i / 3 ][ i % 3 ] = ch - '0';
}
ns.v = ToValue(arr);
ns.r = NIL;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
Input();
bfs();
printf("%s\n", solution);
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|