已知有兩個字串 A$, B$ 及一組字串變換的規則（至多6個規則）:
A1$ -> B1$
A2$ -> B2$
規則的含義爲：在 A＄中的子串 A1$ 可以變換爲 B1$、A2$ 可以變換爲 B2$ …。
例如：A$＝'abcd' B$＝'xyz'
變換規則爲：
‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’
則此時，A$ 可以經過一系列的變換變爲 B$，其變換的過程爲：
‘abcd’->‘xud’->‘xy’->‘xyz’
共進行了三次變換，使得 A$ 變換爲B$。
[輸入]:
鍵盤輸人文件名。文件格式如下：
A$ B$
A1$ B1$ \
A2$ B2$? |-> 變換規則
... ... /?
所有字符串長度的上限爲 20。
[輸出]:
輸出至屏幕。格式如下：
若在 10 步（包含 10步）以內能將 A$ 變換爲 B$ ，則輸出最少的變換步數；否則輸出"NO ANSWER!"
[輸入輸出樣例]
b.in:
abcd wyz
abc xu
ud y
y yz
屏幕顯示：
3
【分析】
很明顯，這是一道搜索題目。當年我寫的時候，那是我有史以來寫的最長的程序。我用了暴力的字符串匹配算法+動態的字典樹優化+兩次廣度優先搜索！
雖然速度尚可，但是代碼太長了。不過其中有100+行是重複的。
【我的代碼】
using namespace std;
/*
*Program:字典树操作
*Author:Yee-fan Zhu
*/
const int sonnum=200; //子节点个数
const char base='\0';
struct Trie
{
bool isStr; //该处是否插入过一个字符串
struct Trie *son[sonnum];//子节点
};
Trie *NewTrie() //Create a new node 建立一个新的字典树
{
Trie *temp=new Trie;
temp->isStr=false;
for (int i=0;i<sonnum;i++)
temp->son[i]=NULL; //初始化子节点
return temp;
}
void Insert(Trie *pnt,char *s,int len) //Insert a new word to Trie Tree
{ //向字典树插入一个新的字符串
Trie *temp=pnt;
for (int i=0;i<len;i++)
{
if (temp->son[s[i]-base]==NULL)
temp->son[s[i]-base]=NewTrie();
temp=temp->son[s[i]-base];
}
temp->isStr=true;
}
bool check(Trie *pnt,char *s,int len) //测试字典树中是否存在某个字符串
{
Trie *temp=pnt;
for (int i=0;i<len;i++)
if (temp->son[s[i]-base]!=NULL)
temp=temp->son[s[i]-base];
else return false;
return temp->isStr;
}
/*字典树的操作函数块*/
char str[21]; //起始字符串
char gol[21]; //目标字符串
struct Bianhuan
{
char Q[21];
int Qlen;
char H[21];
int Hlen;
}change[7];//变换规则
char Queue[10000][21]; //广搜队列
int QTime[10000];
int big=1,small=0;//队头队尾指针
int rul=0;
int minn=11;
ifstream fin("string.in");
ofstream fout("string.out");
void init()
{
fin>>str>>gol;
while(!fin.eof())
{
fin>>change[rul].Q>>change[rul].H;
change[rul].Qlen=strlen(change[rul].Q);
change[rul].Hlen=strlen(change[rul].H);
rul++;
}
}
void print()
{
fout<<str<<" "<<gol<<" "<<rul<<endl;
for (int i=0;i<rul;i++)
fout<<change[i].Q<<" "<<change[i].H<<endl;
return;
}
int pipei(char str1[],char str2[])
{
char *ptr;
ptr=strstr(str1,str2);
if (ptr==NULL) return -1;
return strlen(str1)-strlen(ptr);
}
char res[21];
void strlink(char a[],char b[])
{
memset(res,'\0',sizeof(res));
int len=0;
for (int i=0;i<strlen(a);i++)
{
res[len]=a[i];
len++;
}
for (int j=0;j<strlen(b);j++)
{
res[len]=b[j];
len++;
}
}
int ppp[22];
int pap(char mum[],char kid[]) //字符串的完全匹配
{
int pp=0;
int ml=strlen(mum);
int kl=strlen(kid);
char begin=kid[0];
bool flg=true;
for (int i=0;i<ml;i++)
{
flg=true;
if (begin!=mum[i]) continue;
for (int j=0;j<kl;j++)
{
if (i+j>ml)
{
flg=false;
break;
}
if (mum[i+j]!=kid[j])
{
flg=false;
break;
}
}
if (flg)
{
ppp[pp]=i;
pp++;
}
}
return pp;
}
void bfs()
{
Trie *Tree;
Tree=NewTrie();
QTime[0]=0;
strncpy(Queue[0],str,sizeof(str)); //将str复制到队头
Insert(Tree,str,strlen(str)); //插入字符串
while (small!=big)
{
if (QTime[small]<minn)
{
//fout<<small<<" "<<Queue[small]<<endl;
char temp[21];
strncpy(temp,Queue[small],sizeof(Queue[small]));
/*Check*/
if (strcmp(temp,gol)==0)
{
// fout<<"Yes"<<" ";
minn=QTime[small];
}
for (int i=0;i<rul;i++)
{
int pp=pipei(temp,change[i].Q);
if (pp!=-1)
{
char temp2[21];
memset(temp2,'\0',sizeof(temp2));
for (int j=0;j<pp;j++)
temp2[j]=temp[j];
strlink(temp2,change[i].H);
strncpy(temp2,res,sizeof(res));
//for (int m=0;m<strlen(res);m++)
//temp2[m]=res[m];
int len=strlen(temp2);
for (int j=pp+change[i].Qlen;j<strlen(temp);j++)
{
temp2[len]=temp[j];
len++;
}
if (!check(Tree,temp2,strlen(temp2)))
{
Insert(Tree,temp2,strlen(temp2));
strncpy(Queue[big],temp2,sizeof(temp2));
QTime[big]=QTime[small]+1;
big++;
//fout<<small<<" "<<big<<" "<<temp2<<" "<<QTime[big-1]<<endl;
}
}
}
//fout<<endl;
}
small++;
}
}
void bfs2()
{
big=1,small=0;//队头队尾指针
Trie *Tree2;
Tree2=NewTrie();
QTime[0]=0;
strncpy(Queue[0],str,sizeof(str)); //将str复制到队头
Insert(Tree2,str,strlen(str)); //插入字符串
while (small!=big)
{
if (QTime[small]<minn)
{
//fout<<small<<" "<<Queue[small]<<endl;
char temp[21];
strncpy(temp,Queue[small],sizeof(Queue[small]));
/*Check*/
if (strcmp(temp,gol)==0)
{
// fout<<"Yes"<<" ";
minn=QTime[small];
}
for (int i=0;i<rul;i++)
{
int pp=pipei(temp,change[i].Q);
if (pp!=-1)
{
int point=pap(temp,change[i].Q);
for(int p=0;p<point;p++)
{
pp=ppp[p];
char temp2[21];
memset(temp2,'\0',sizeof(temp2));
for (int j=0;j<pp;j++)
temp2[j]=temp[j];
strlink(temp2,change[i].H);
strncpy(temp2,res,sizeof(res));
// for (int m=0;m<strlen(res);m++)
//temp2[m]=res[m];
int len=strlen(temp2);
for (int j=pp+change[i].Qlen;j<strlen(temp);j++)
{
temp2[len]=temp[j];
len++;
}
if (!check(Tree2,temp2,strlen(temp2)))
{
Insert(Tree2,temp2,strlen(temp2));
strncpy(Queue[big],temp2,sizeof(temp2));
QTime[big]=QTime[small]+1;
big++;
//fout<<small<<" "<<big<<" "<<temp2<<" "<<QTime[big-1]<<endl;
}
}
}
}
//fout<<endl;
}
small++;
}
}
int main()
{
init();
//print();
//fout<<endl;
bfs();
if (minn==11)
{
bfs2();
if (minn==11) fout<<"NO ANSWER!"<<endl;
else fout<<minn<<endl;
}
else fout<<minn<<endl;
return 0;
}
沒有留言:
張貼留言