http://acm.hdu.edu.cn/showproblem.php?pid=1430整整花了我兩天時(shí)間。。。
唉。。。本來(lái)以為是很簡(jiǎn)單的
寫(xiě)完八數(shù)碼后知道了逆序數(shù)一個(gè)hash函數(shù)
以為寫(xiě)這題也可以這樣做
很簡(jiǎn)單的寫(xiě)好后提交結(jié)果是TLE。。。唉，數(shù)據(jù)量太大了。。。
雖然說(shuō)最多只有40320個(gè)狀態(tài)，但由于in文件太大，有40KB，會(huì)導(dǎo)致超時(shí)。
所以請(qǐng)教了高杰之后知道可以用雙向廣搜處理。
這樣時(shí)間就少了很多很多
應(yīng)為廣搜到后邊狀態(tài)是指數(shù)級(jí)別增長(zhǎng)的
但是寫(xiě)阿寫(xiě)，總是寫(xiě)不對(duì)，關(guān)鍵是字典序最小的那過(guò)很難處理，看了高杰的代碼后還不知所然。。
昨天晚上請(qǐng)教了linle大牛，他是這題時(shí)間最短的人，只用了15MS，用雙向廣搜至少都要2000MS+
他一語(yǔ)道破玄機(jī)，“預(yù)處理”，所有狀態(tài)到12345678全部先處理出來(lái)
于是我就在想預(yù)處理之后能怎么做。。
先預(yù)處理說(shuō)所有狀態(tài)到12345678的字典序最小的最優(yōu)解
今天終于想出來(lái)了。每個(gè)初始狀態(tài)都可以轉(zhuǎn)化成12345678
比如拿
47586312
87654321來(lái)說(shuō)
可以轉(zhuǎn)化成
12345678
42531687
接下來(lái)就簡(jiǎn)單了
根據(jù)預(yù)處理出來(lái)的路徑打印。。。
#include<stdio.h>
#include<string>
#define Max 40321
char num[Max][9];
int hash[Max];
int father[Max];
int ku[] = {1,1,2,6,24,120,720,5040};
char act[Max];
int hash_code(char *a)
{
int i,j,cnt,sum=0;
for(i=0;a[i];i++)
{
cnt = 0;
for(j=0;j<i;j++)
{
if(a[j]>a[i])
cnt ++;
}
sum += cnt*ku[i];
}
return sum;
}
void change(char *a,char *b,int s)
{
int i;
char c;
switch (s)
{
case 0:
strcpy(a,b);
strrev(a);
return ;
case 1:
a[0] = b[3];
for(i=0;i<3;i++)
a[i+1] = b[i];
a[7] = b[4];
for(i=5;i<=7;i++)
a[i-1] = b[i];
a[8] = 0;
return ;
case 2:
strcpy(a,b);
c = a[5];
a[5] = a[2];
a[2] = a[1];
a[1] = a[6];
a[6] = c;
return ;
}
}
void bfs()
{
int head,tail,i,key;
head = tail = 0;
char next[9];
for(i=0;i<8;i++)
num[0][i] = i+'1';
num[0][i] = 0;
memset(hash,-1,sizeof(hash));
hash[hash_code(num[0])] = 0;
while(head <= tail)
{
for(i=0;i<3;i++)
{
change(next,num[head],i);
key = hash_code(next);
if(hash[key]==-1)
{
tail ++;
hash[key] = tail;
strcpy(num[tail],next);
act[tail] = 'A' + i;
father[tail] = head;
}
}
head ++;
}
tail = 0;
}
int main()
{
char start[9],end[9],ans[100];
int pos[9],i,key;
bfs();
while(scanf("%s%s",start,end)==2)
{
for(i=0;i<8;i++)
pos[start[i]-'1'] = i;
for(i=0;i<8;i++)
end[i] = pos[end[i]-'1'] +'1';
end[8] = 0;
key = hash[hash_code(end)];
i = 0;
while(key)
{
ans[i++] = act[key];
key = father[key];
}
ans[i] = 0;
strrev(ans);
puts(ans);
}
return 0;
}
posted on 2009-02-27 16:41
shǎ崽 閱讀(1204)
評(píng)論(5) 編輯 收藏 引用