#include <cstring>
#include <cstdlib>
#include <cstdio>
#define INPUT
using namespace std;
/**
Problem : poj1077,hdu1043,經典的八數位問題。
知識點: BFS + HASH + 打表 + 父親節點記錄
境界:3 - BFS+HASH+打表
A了兩天!!!
記得拿啟發式,雙向BFS重新寫一遍
IDA*就不做要求了。。。
思路:
1.打表 + 輸出
将每個狀态記錄成0..9的一個排列。0代表的是'x'的位置。
每個狀态用康托展開,求出自己的唯一id,然後搜尋的下一個狀态的
fa[id_next] = id_now,然後move[id_next] = i;
dis[id_next] = dis[id_now] + 1;
這樣,根據目标狀态,求出其對應的康托展開,然後根據
fa[]數組就能找到每個移動。dis是指從1234567890到目标節點的最短steps
根據CLRS,BFS能找到兩個節點中的最短路徑。
注意邊界,我們是反向搜尋的,從目标狀态往回搜尋是這麼搜尋的:
int j = id_dest;
for(int k = dis[id_dest]; k > 0 ; k--,j = fa[j] )
{
printf("%d",move[j]);
}
因為達到了dest 就不再移動,是以move[id_dest]記錄的是最後一次的移動
一點一點往前輸出也就是了,但是注意記錄的是從"1234567890"移動到目标
狀态的方式,是以對于 1234567890 的向左移動,在這裡就變成了向右移動
(也就是說,把整個過程反過來),是以要反着輸出。
2.搜尋
搜尋的時候判重問題,重複的狀态不再進行搜尋,利用hash表進行搜尋,
按照PP的解釋這樣查詢的效率是O(1)
每個狀态看做一個整數,然後
hash_id = nownum % HASHKEY;
注意hash表下标一定要從1開始!!!
也就是下文的now從1開始!否則next[hash_id]可以為0!!那就惡心死了!
while(next[hash_id])
{
if states[ next[hash_id] ] == nownum return 0; //插入失敗
hash_id = next[ hash_id ];
}
next[ hash_id ] = now;
states[now] = nownum;
now++;
return true;
如果hashkey相同且發現了相同的狀态,那麼就傳回失敗,如果傳回失敗,那麼就不展開該節點進行搜尋了。
教訓:
這題正向不行就應該想到打表,尤其是康托展開+逆序數的應用是一個亮點!詳細看
Cantor那個代碼。cantor[]這個數組還記錄了排列所需要用的階乘數目。
這道題雙向BFS,A*,IDA*都能做,是以是一道好題,第三重境界,還需要加油!
還有輸出的反向輸出,父節點的記錄,各個都是那麼巧妙,這道題要多看幾遍
*/
const int c0de4fun = 364880;
const int HASHKEY = 1000003;
//l r u d
//r,l,d,u
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const int cantor[] = {1,1,2,6,24,120,720,5040,40320};
//int vals[c0de4fun];
int head[HASHKEY];
int next[HASHKEY];
int states[HASHKEY];
int queue[c0de4fun];
int dis[c0de4fun];
int fa[c0de4fun];
int move[c0de4fun];
int now = 1,front = 1 ,rear = 2;
int _dest[9];
int hashk(int node)
{
return node % HASHKEY;
}
bool insert(int node)
{
int key = hashk(node);
while ( next[key] )
{
if( states[ next[key] ] == node ) return false;
key = next[key];
}
next[key] = now;
states[now] = node;
now++;
return 1;
}
void segNum(int* tmp,int node)
{
for(int i = 8 ; i >= 0 ; i--)
{
tmp[i] = node % 10;
node /= 10;
}
}
int getNum(int* tmp)
{
int res = 0;
for(int i = 0 ; i < 9 ; i++)
{
res = res*10 + tmp[i];
}
return res;
}
int getCanto(int *a)
{
int ans = 0 ;
int i,j,cnt;
for( i = 0 ; i < 9 ;i++)
{
cnt = 0;
for( j = i + 1; j < 9; j++)
{
// if(a[i] < a[j]) cnt++;
if( a[i] > a[j] ) cnt++;
}
ans = ans + cantor[ 8 - i ] * cnt;
}
return ans;
}
void bfs(int node)
{
int i,x,y,newx,newy,z,newz;
int tmp[9];
int tmp1[9];
int tnode,tnode1;
// int front = 1 ,rear = 2;
fa[0] = 0;
dis[0] = 0;
queue[front] = node;
insert(node);
while(front < rear)
{
tnode = queue[front];
//insert(tnode);
segNum(tmp,tnode);
for( i = 0 ; i < 9; i++)
{
if ( tmp[i] == 0 ) break; //找到X的位置
}
x = i / 3 ; y = i % 3;
z = i;
for( i = 0 ; i < 4 ; i++)
{
newx = x + dx[i];
newy = y + dy[i];
if( newx >= 0 && newx < 3 && newy >=0 && newy < 3)
{
///合法移動
newz = newx * 3 + newy;
memcpy(tmp1,tmp,sizeof(tmp));
tmp1[newz] = tmp[z];
tmp1[z] = tmp[newz];
tnode = getNum(tmp1);
if ( insert(tnode) )
{
int cant_tmp = getCanto(tmp);
int cant_tmp1 = getCanto(tmp1);
///這裡用康托展開給tnode一個值,然後
///也給tnode1一個值,fa[kan_tnode1] = kan_node;
///然後move[kan_node] = 對應值。
fa[cant_tmp1] = cant_tmp;
move[cant_tmp1] = i;
dis[cant_tmp1] = dis[cant_tmp] + 1;
queue[rear] = tnode;
rear++;
}
}
}
front++;
}
#ifdef TEST
for(int i = 0 ; i < 9 ; i++)
{
printf("%d ",tmp[i]);
}
#endif
}
void Solve()
{
int k = getNum(_dest);
int l = 0;
int ind;
bool isSoluted = false;
for(int i = 1 ; i < rear; i++)
{
if ( k == queue[i] )
{
// printf("Can be solved\n");
isSoluted = true;
break;
}
}
if( isSoluted )
{
ind = getCanto(_dest);
l = ind;
for( k = dis[ind] ;k > 0;k--,l = fa[l])
{
switch(move[l])
{
case 0 :
// printf("l ");
printf("r");
break;
case 1:
// printf("r");
printf("l");
break;
case 2:
// printf("u ");
printf("d");
break;
case 3:
printf("u");
// printf("d ");
break;
}
// printf("%d ",move[k]);
}
printf("\n");
// printf("Solved\n");*/
}
else
{
printf("unsolvable\n");
}
}
int main()
{
char tmp1;
int i = 0;
#ifdef INPUT
freopen("b:\\acm\\poj1077\\input.txt","r",stdin);
#endif
bfs(123456780);
while ( scanf("%c",&tmp1) != EOF )
{
if (tmp1 == ' ' || tmp1 == '\n') continue;
if (tmp1 == 'x' )
{
_dest[i] = 0;
}
else
{
_dest[i] = tmp1 - '0';
}
i++;
if( i % 9 == 0)
{
Solve();
i = 0;
}
}
return 0;
}