【NOIP2002提高组T2】字串变换-双向BFS或迭代加深搜索

做法：这道题...比较玄学，网上大多数人的题解都是双向BFS，这里就不赘述了。但我认为，还有一种迭代加深搜索的算法，但是肯定比双向BFS要慢...在Vijos上这两种方法都过了，放在这里让大家参考。

以下是本人代码（本人水平不行，代码非常丑，凑合着看吧）：

双向BFS：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct str {char s[30];} a[10],b[10];
str q1[10010],q2[10010];
int tot=0,step=0;
bool f=0;

bool cmp(str a,str b)
{
  if (strlen(a.s)!=strlen(b.s)) return 0;
  else
  {
    int len=strlen(a.s);
    for(int i=0;i<len;i++)
	  if (a.s[i]!=b.s[i]) return 0;
	return 1;
  }
}

void double_bfs()
{
  int h1=1,h2=1,t1=1,t2=1;
  q1[1]=a[0];q2[1]=b[0];
  int f1=1,f2=1,s1=1,e1=1,s2=1,e2=1;
  if (cmp(a[0],b[0])) {f=1;return;}
  while(h1<=t1&&h2<=t2&&step<=10)
  {
    if (f1<=f2)
	{
	  str now=q1[h1++];
	  for(int i=s2;i<=e2;i++)
	    if (cmp(now,q2[i])) {f=1;return;}
	  int len=strlen(now.s);
	  for(int i=1;i<=tot;i++)
	    for(int j=0;j<len;j++)
		  if (j+strlen(a[i].s)-1<len&&a[i].s[0]==now.s[j])
		  {
		    bool flag=1;
		    for(int k=1;k<strlen(a[i].s);k++)
			  if (a[i].s[k]!=now.s[j+k]) {flag=0;break;}
			if (flag)
			{
			  str nxt;
			  memset(nxt.s,0,sizeof(nxt.s));
			  for(int k=0,l=0;k<=strlen(now.s);k++,l++)
			  {
			    if (k==j)
				{
				  int x;
				  for(x=0;x<strlen(b[i].s);x++)
				    nxt.s[l+x]=b[i].s[x];
				  l=l+x-1;
				  k=j+strlen(a[i].s)-1;
				}
				else nxt.s[l]=now.s[k];
			  }
			  q1[++t1]=nxt;
			}
		  }
	  if (h1>e1)
	  {
	    step++;
		f1=t1-e1;
		s1=e1+1;
	    e1=t1;
	  }
	}
	else
	{
	  str now=q2[h2++];
	  for(int i=s1;i<=e1;i++)
	    if (cmp(now,q1[i])) {f=1;return;}
	  int len=strlen(now.s);
	  for(int i=1;i<=tot;i++)
	    for(int j=0;j<len;j++)
		  if (j+strlen(b[i].s)-1<len&&b[i].s[0]==now.s[j])
		  {
		    bool flag=1;
		    for(int k=1;k<strlen(b[i].s);k++)
			  if (b[i].s[k]!=now.s[j+k]) {flag=0;break;}
			if (flag)
			{
			  str nxt;
			  memset(nxt.s,0,sizeof(nxt.s));
			  for(int k=0,l=0;k<=strlen(now.s);k++,l++)
			  {
			    if (k==j)
				{
				  int x;
				  for(x=0;x<strlen(a[i].s);x++)
				    nxt.s[l+x]=a[i].s[x];
				  l=l+x-1;
				  k=j+strlen(b[i].s)-1;
				}
				else nxt.s[l]=now.s[k];
			  }
			  q2[++t2]=nxt;
			}
		  }
	  if (h2>e2)
	  {
	    step++;
		f2=t2-e2;
		s2=e2+1;
	    e2=t2;
	  }
	}
  }
  f=0;
}

int main()
{
  while(scanf("%s%s",a[tot].s,b[tot].s)!=EOF)
  {
    getchar();
	tot++;
  }
  tot--;
  
  double_bfs();
  
  if (f) printf("%d",step);
  else printf("NO ANSWER!");
  
  return 0;
}

迭代加深搜索：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
struct str {char s[30];} a[10],b[10];
int tot,depth;

bool cmp(str a,str b)
{
  if (strlen(a.s)!=strlen(b.s)) return 0;
  for(int i=0;i<strlen(a.s);i++)
    if (a.s[i]!=b.s[i]) return 0;
  return 1;
}

bool dfs(int step,str now)
{
  if (step==depth) return cmp(now,b[0]);
  for(int i=1;i<=tot;i++)
    for(int j=0;j<strlen(now.s);j++)
	  if (now.s[j]==a[i].s[0]&&j+strlen(a[i].s)-1<strlen(now.s))
	  {
	    bool flag=1;
		for(int k=1;k<strlen(a[i].s);k++)
		  if (now.s[j+k]!=a[i].s[k]) {flag=0;break;}
		if (flag)
		{
		  str nxt;
		  memset(nxt.s,0,sizeof(nxt.s));
		  for(int k=0,l=0;k<strlen(now.s);k++,l++)
		  {
		    if (k==j)
			{
			  for(int x=0;x<strlen(b[i].s);x++)
			    nxt.s[l+x]=b[i].s[x];
			  l=l+strlen(b[i].s)-1;
			  k=j+strlen(a[i].s)-1;
			}
			else nxt.s[l]=now.s[k];
		  }
		  if (dfs(step+1,nxt)) return 1;
		}
	  }
  return 0;
}

int main()
{
  tot=0;
  while(scanf("%s%s",a[tot].s,b[tot].s)!=EOF)
  {
	tot++;
	getchar();
  }
  tot--;
  
  for(depth=0;depth<=10;depth++)
    if (dfs(0,a[0])) break;
  
  if (depth<=10) printf("%d",depth);
  else printf("NO ANSWER!");
  
  return 0;
}