洛谷P1032：https://www.luogu.org/problemnew/show/P1032
思路
初看题目觉得挺简单的一道题
但是仔细想了一下发现实现代码挺麻烦的
而且2002年的毒瘤输入是什么鬼啊 连组数都没有的真的好吗
这道题参考了题解才完成
需要用到我从来没有用过的map来判重
然后就是广搜+string的一些自带函数运用
PS：这道题本地测试数据时要用Ctrl+Z+回车才可以出ans
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
#define maxn 15
map<
string,
int> m;
//map用来判重
string a,b;
string c[maxn],d[maxn];
int n,ans;
struct node
//自定义结构体方便调用
{
string str;
//字符串
int sum;
//步数
};
queue <node> q;
//队列
string change(
const string &str,
int i,
int j)
{
string t=
"";
if(i+c[j].length()>str.length())
return t;
//长度超过就不可以替换
for(
int k=
0;k<c[j].length();k++)
//枚举判断是否可以替换
if(str[i+k]!=c[j][k])
return t;
t=str.substr(
0,i);
//新串的前面没有改变
t+=d[j];
//加上替换之后的串
t+=str.substr(i+c[j].length());
//加上需要替换的串的后面不需要替换的串
return t;
}
int main()
{
cin>>a>>
b;
while(cin>>c[n]>>d[n]) n++;
//毒瘤输入
node s;
s.str=a;
//初始的串
s.sum=
0;
q.push(s);
while(!q.empty())
//BFS
{
node x=q.front();
//取出队列头
q.pop();
//删除头
string temp;
if(m.count(x.str)==
1)
continue;
//判重
if(x.str==b)
//如果已经满足
{
ans=
x.sum;
break;
}
m[x.str]=
1;
//这种字符串已经尝试过
for(
int i=
0;i<x.str.length();i++)
//从头枚举哪里可以替换
{
for(
int j=
0;j<n;j++)
//枚举替换方案
{
temp=change(x.str,i,j);
//替换
if(temp!=
"")
//如果可以替换
{
node y;//加入队列
y.str=
temp;
y.sum=x.sum+
1;
q.push(y);
}
}
}
}
if(ans>
10||(!ans))
//注意ans同样不能为0
cout<<
"NO ANSWER!";
else
cout<<
ans;
}
转载于:https://www.cnblogs.com/BrokenString/p/9845900.html
相关资源：JAVA上百实例源码以及开源项目
