题目描述
已知有两个字串A,B及一组字串变换的规则（至多6个规则）:
A_1->B_1
A_2-> B_2
规则的含义为：在 A中的子串 A_1可以变换为B_1，A_2可以变换为 B_2……。
例如：A=abcd，B＝xyz，
变换规则为：
abc→xu，ud→y，y→yz
则此时，A可以经过一系列的变换变为B，其变换的过程为：
abcd→xud→xy→xyz。
共进行了3次变换，使得A变换为B。
输入格式
输入格式如下：
AA BB
A_1 B_1
A_2 B_2|-> 变换规则
... ... /所有字符串长度的上限为20。
输出格式
输出至屏幕。格式如下：
若在10步（包含10步）以内能将A变换为B，则输出最少的变换步数；否则输出"NO ANSWER!"
输入输出样例
输入 #1
abcd xyz
abc xu
ud y
y yz
输出 #1
3
反思
看到难度评级先不要怕，也不要急着看答案，先自己多想想。
源码
#include<bits/stdc++.h>
using namespace std;
int n = 0;
string A, B;
string a[7], b[7];
queue<string> s;
queue<int> bs;
map<string, int> m;
int bfs()
{
string S;
while (!s.empty() && bs.front() <= 10 && s.front() != B)
{
if (m[s.front()] == 1)
{
s.pop();
bs.pop();
continue;
}
m[s.front()] = 1;
for (int i = 0; i < n; i++)
{
int temp = 0;
while ((temp=s.front().find(a[i], temp))!=A.npos)//查出所有字串
{
S = s.front();
S.replace(temp, a[i].size(), b[i]);
s.push(S);
bs.push(bs.front() + 1);
temp++;
}
}
s.pop();
bs.pop();
}
if (s.empty() || bs.front() > 10)
return -1;
else
return bs.front();
}
int main()
{
cin >> A >> B;
while (cin >> a[n] >> b[n])
n++;
while (n == 0 && A != B)
{
cout << "NO ANSWER!";
return 0;
}
s.push(A);
bs.push(0);
int answer = bfs();
if (answer == -1)
cout << "NO ANSWER!";
else
cout << answer;
return 0;
}
