喜欢的话就坚持吧

9月 13

0.00 avg. rating (0% score) - 0 votes

点击了解详情↓

我太菜了,根本不会用什么stl的各种函数,c++11基本不会,但noip考各种stl的奇技淫巧,(不然代码很难写)。必须学一些stl的使用了。

题目大意 给你两个字符串a,b(长度<=20)和不多于6个变换规则,问a能否经过不超过10次变换变成b.
例如;a: abcd b: xyz
有三种变化分别为
     abc->xu
     ud->y
     y->yz

我们手玩可以发现经过3次就可以;(自己玩去)
基本读完题就知道是个爆搜,流程大概是
1:读入(废话)
2:bfs搜所有更改可能(敌法师(dfs)不该你出场)
3:输出

考虑设计bfs,开一个map判重,queue里面放struct存状态,string优化代码;
差不多了,可以写了;
等等,上面的stl我一个都不会。
那就学啊,能过编译就行,
……
临时学了30min+写完的代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>


using namespace std;
int tot=1,ans=0x3f3f3f3f;
string a1,b1,c1,d1;
map<string,int> mp;
pair<string,string> pr;
vector<pair<string,string> > v;
struct data
{
    string ch;int tim;
};
queue<data> q;
int main()
{
    cin>>a1>>b1;
    while(cin>>c1>>d1){pr.first=c1,pr.second=d1;v.push_back(pr);}//开一个vector存变化
    data pack=(data){a1,0};
    q.push(pack);
    while(!q.empty())//爆搜
    {
        data now=q.front();q.pop();
        if(now.ch==b1)//如果成功就输出
        {
            ans=min(ans,now.tim);
            if(ans>10) {printf("NO ANSWER!");return 0;}
            else {printf("%d\n",ans);return 0;}
        }
        vector<pair<string,string> >::iterator it;
        for(it=v.begin();it!=v.end();++it)//遍历所有变化
        {
            string tm=now.ch;
            string tmd;
            pr.first=it->first;
            pr.second=it->second;
            int pos=tm.find(pr.first);//找到能换的位置
            while(pos!=tm.npos)
            {
                tmd=tm.substr(0,pos);//string内置函数修改
                tmd=tmd+pr.second;
                tmd+=tm.substr(pos+pr.first.size());
                if(now.tim+1<mp[tmd]||mp[tmd]==0)
                {
                    data pack=(data){tmd,now.tim+1};
                    q.push(pack);mp[tmd]=now.tim+1;
                }
                pos=tm.find(pr.first,pos+1);
            }
        }
    }
    printf("NO ANSWER!");
}
//感觉也没什么。

0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注