http://acm.hdu.edu.cn/showproblem.php?pid=1430整整花了我兩天時間。。。
唉。。。本來以為是很簡單的
寫完八數碼后知道了逆序數一個hash函數
以為寫這題也可以這樣做
很簡單的寫好后提交結果是TLE。。。唉，數據量太大了。。。
雖然說最多只有40320個狀態，但由于in文件太大，有40KB，會導致超時。
所以請教了高杰之后知道可以用雙向廣搜處理。
這樣時間就少了很多很多
應為廣搜到后邊狀態是指數級別增長的
但是寫阿寫，總是寫不對，關鍵是字典序最小的那過很難處理，看了高杰的代碼后還不知所然。。
昨天晚上請教了linle大牛，他是這題時間最短的人，只用了15MS，用雙向廣搜至少都要2000MS+
他一語道破玄機，“預處理”，所有狀態到12345678全部先處理出來
于是我就在想預處理之后能怎么做。。
先預處理說所有狀態到12345678的字典序最小的最優解
今天終于想出來了。每個初始狀態都可以轉化成12345678
比如拿
47586312
87654321來說
可以轉化成
12345678
42531687
接下來就簡單了
根據預處理出來的路徑打印。。。
#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ǎ崽 閱讀(1203)
評論(5) 編輯 收藏 引用