[NOIP2002 提高组] 字串变换
题目背景
本题疑似错题,不保证存在靠谱的多项式复杂度的做法。测试数据非常的水,各种做法都可以通过,不代表算法正确。因此本题题目和数据仅供参考。
题目描述
已知有两个字串 \(A,B\) 及一组字串变换的规则(至多 \(6\) 个规则),形如:
- \(A_1\to B_1\)。
- \(A_2\to B_2\)。
规则的含义为:在 \(A\) 中的子串 \(A_1\) 可以变换为 $ B_1\(,\)A_2$ 可以变换为 \(B_2\cdots\)。
例如:\(A=\texttt{abcd}\),\(B=\texttt{xyz}\),
变换规则为:
- \(\texttt{abc}\rightarrow\texttt{xu}\),\(\texttt{ud}\rightarrow\texttt{y}\),\(\texttt{y}\rightarrow\texttt{yz}\)。
则此时,\(A\) 可以经过一系列的变换变为 \(B\),其变换的过程为:
- \(\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}\)。
共进行了 \(3\) 次变换,使得 \(A\) 变换为 \(B\)。
输入格式
第一行有两个字符串 \(A,B\)。
接下来若干行,每行有两个字符串 \(A_i,B_i\),表示一条变换规则。
输出格式
若在 \(10\) 步(包含 \(10\) 步)以内能将 \(A\) 变换为 \(B\),则输出最少的变换步数;否则输出 NO ANSWER!
。
样例 #1
样例输入 #1
abcd xyz
abc xu
ud y
y yz
样例输出 #1
3
提示
对于 \(100\%\) 数据,保证所有字符串长度的上限为 \(20\)。
【题目来源】
NOIP 2002 提高组第二题
思路:使用bfs暴力搜索所有的情况,第一次出现时所经过的步骤就是最优解
最开始的时候我其实犯了一个错误,就是没有意识到一个相同的字符串是可以转换成不同的字符串(测试点1),由此我将转换关系用unordered_map来存储,导致一个字符串只存在一种对应关系。修改后使用pair来存储。这也提醒了我在题目没有明确说明唯一对应关系的条件下,盲目使用类似哈希表一一的对应结构是一种不负责任的行为
第一次代码提交
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
queue <string> q;
string final_str,begin_str,end_str="this_is_end_str";
vector<pair<string,string>>change;
const int MAX_STEP=10;
void bfs()
{
int ans=0;
q.push(begin_str);
q.push(end_str);
while(!q.empty()&&ans<=MAX_STEP)
{
string first=q.front();
q.pop();
if(first==end_str)
{
ans++;
q.push(end_str);
continue;
}
for(auto change_str:change)
{
int pos=0;
while((pos=first.find(change_str.first,pos))!=string::npos)
{
string temp=first;
temp.insert(pos+change_str.first.size(),change_str.second);
q.push(temp.replace(pos,change_str.first.size(),""));
pos++;
if(q.back()==final_str)
{
cout<<ans+1<<endl;
return;
}
}
}
}
if(ans>MAX_STEP)cout<<"NO ANSWER!"<<endl;
}
int main()
{
cin>>begin_str>>final_str;
pair<string,string>temp;
while(cin>>temp.first>>temp.second)change.push_back(temp);
bfs();
return 0;
}
第二次代码优化
使用unordered_map进行优化,记录已经操作过的字符串,再次出现便不再压入队列中去
这次优化后代码速度和内存消耗少了许多,由于数据太水,上一个提交竟然能通过。这次提交能通过题解中大佬们提供的额外数据,但是上一个。。。。。。(我随便复制了个数据都过不了,直接卡住了。。。。)
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <unordered_map>//记录重复操作字符串
using namespace std;
queue <string> q;
unordered_map<string,int>map;
string final_str,begin_str,end_str="this_is_end_str";
vector<pair<string,string>>change;
const int MAX_STEP=10;
void bfs()
{
int ans=0;
q.push(begin_str);
q.push(end_str);
while(!q.empty()&&ans<=MAX_STEP)
{
string first=q.front();
q.pop();
if(first==end_str)
{
ans++;
q.push(end_str);
continue;
}
for(auto change_str:change)
{
int pos=0;
while((pos=first.find(change_str.first,pos))!=string::npos)
{
string temp=first;
temp.insert(pos+change_str.first.size(),change_str.second);
temp.replace(pos,change_str.first.size(),"");
if(!map[temp])
{
map[temp]++;
q.push(temp);
if(temp==final_str)
{
cout<<ans+1<<endl;
return;
}
}
pos++;
}
}
}
if(ans>MAX_STEP)cout<<"NO ANSWER!"<<endl;
}
int main()
{
cin>>begin_str>>final_str;
pair<string,string>temp;
while(cin>>temp.first>>temp.second)change.push_back(temp);
bfs();
return 0;
}
标签:temp,NOIP2002,变换,texttt,字串,str,include,rightarrow
From: https://www.cnblogs.com/jyhlearning/p/16722602.html