調試了將近一個小時！我美好的一個夜晚啊！就這樣浪費了！
而不斷WA的原因竟然是因為輸出格式問題！最后一組數據后面多了一個回車！
再次抱怨ACM的多組數據測試！抱怨全文比較！抱怨不提示PE提示WA！
好了，STOP！
這題BFS求最短路即可。雖然可能有25000個單詞，相當于25000個結點，構圖的話空間肯定不夠，時間也不允許。但是因為單詞長度不同的肯定不會是doublet，所以平均下來一個圖的結點數大約25000/16個，O(n^2)的算法足夠了。
在讀入是就把不同長度的單詞分開，BFS讓字符串進隊列，只需要讓該字符串所在位置編號入隊即可。
以下是我的代碼：
#include<iostream>
#include<fstream>
#include<string>
#include<bitset>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxl 17
#define maxn 25147
using namespace std;
typedef struct
{
long counter,front,rear,pos[maxn];
}queue;
void Clear(queue &q)
{
q.counter=0;q.front=0;q.rear=-1;
}
bool Empty(queue &q)
{
return (q.counter==0);
}
void Push(queue &q,long x)
{
q.counter++;
q.rear++;
q.pos[q.rear]=x;
}
void Pop(queue &q,long &x)
{
q.counter--;
x=q.pos[q.front];
q.front++;
}
long T=0,cnt[maxl];
string word[maxl][maxn];
queue q;
bool doublet(string &a,string &b)
{
long l=a.length(),diff=0;
for(long i=0;i<l;i++)
if(a[i]!=b[i])
{
diff++;
if(diff>=2) return false;
}
if(!diff) return false;
return true;
}
int main()
{
memset(cnt,0,sizeof(cnt));
string t;
while(getline(cin,t)&&!t.empty())
{
cnt[t.length()]++;
word[t.length()][cnt[t.length()]]=t;
}
string a,b;
while(cin>>a>>b)
{
T++;
long la=a.length(),pa,lb=b.length(),pb;
long d[maxn],f[maxn];
bool used[maxn];
if(la!=lb)
{
if(T>=2) cout<<endl;
cout<<"No solution."<<endl;
continue;
}
for(pa=1;pa<=cnt[la];pa++)
if(word[la][pa]==a)
break;
for(pb=1;pb<=cnt[la];pb++)
if(word[la][pb]==b)
break;
if(pa>cnt[la]||pb>cnt[la])
{
if(T>=2) cout<<endl;
cout<<"No solution."<<endl;
continue;
}
memset(d,-1,sizeof(d));
memset(f,0,sizeof(f));
memset(used,false,sizeof(used));
Clear(q);
Push(q,pa);d[pa]=0;f[pa]=0;used[pa]=true;
while(!Empty(q))
{
long r;
Pop(q,r);
for(long i=1;i<=cnt[la];i++)
if(!used[i]&&doublet(word[la][r],word[la][i]))
{
Push(q,i);
d[i]=d[r]+1;
f[i]=r;
used[i]=true;
}
if(d[pb]!=-1) break;
}
if(d[pb]==-1)
{
if(T>=2) cout<<endl;
cout<<"No solution."<<endl;
}
else
{
if(T>=2) cout<<endl;
long num=0,ans[maxn];
num++;ans[num]=pb;
while(f[pb])
{
num++;ans[num]=f[pb];
pb=f[pb];
}
for(long i=num;i>=1;i--)
cout<<word[la][ans[i]]<<endl;
}
}
return 0;
}
posted on 2010-11-15 00:02
lee1r 閱讀(1158)
評論(3) 編輯 收藏 引用 所屬分類:
題目分類：圖論