校内比赛单词序列

爱被打了一巴掌 2021-12-17 01:11 180阅读 0赞

**单词序列**

![1606003-20190612151920378-441349812.png][]

![1606003-20190612151940199-1627976925.png][]

**题解**

不得不说，一遇到字符串啊怕不是就要凉了，不过不要害怕，我们仔细研究一下

1.输入

输入起始字符串，终点字符串，字典

当输入回车键，说明字典已经输完了

![1606003-20190612152709952-1401161315.png][]

string可以直接用cin输入，s.size()可以直接得到长度，可以直接用“=”比较是否相同

scanf读入C字符串， char\[\]那种，

string大概只能cin

2.判断字符串a到b能否一步到达

（1）如果他们长度都不相同，那就一定不能一步到达

（2）如果他们两个单词当中有一个字母不同，那就一定可以一步到达

3.广搜求解

（1）起点入队，标记一步

（2）队列非空就一直进行BFS

（3）取出队首，如果是最终答案，就返回队首的步数

（4）如果可以一步到达，返回队首步数+1

（5）否则，枚举所有没有使用过的单词，看看由当前状态是否可以一步转化，如果可以，就转化           一步成为新的状态，步数+1

（6）如果最终都没有在BFS过程中输出步数的话，那就是无解，输出0

**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<cstdlib>
    
    using namespace std;
    
    string start,end,s[35];
    int n=0;
    bool vis[35];
    
    struct node
    {
        string st;
        int step;
    };
    queue<node>q;
    
    bool nyb(string a,string b)  //a->b能否一步到达 
    {
        if(a.size() !=b.size() )  return 0;
        int dif=0;
        for(int i=0;i<a.size() ;i++)
          if(a[i]!=b[i]) dif++;
        
        return dif==1;
        
    }
    
    int bfs()  //广搜求解 
    {
        memset(vis,false,sizeof(vis));
        
        q.push((node){start,1});
        while(!q.empty() )
        {
            node now=q.front() ;
            q.pop() ;
            if(now.st ==end) return now.step ;
            if(nyb(now.st ,end)) return now.step +1;
            for(int i=1;i<=n;i++)   //枚举没有查过的单词 
            {
                if(!vis[i]&&nyb(now.st ,s[i]))  //一步转化 
                {
                    vis[i]=1;
                    q.push((node){s[i],now.step +1}) ;
                }
            }
        }
        return 0;
    }
    
    int main()
    {
        cin>>start>>end;
    while(cin>>s[++n])
        {
            if(getchar()=='\n')  break;
        }
        cout<<bfs();
        return 0;
    }

转载于:https://www.cnblogs.com/xiaoyezi-wink/p/11010023.html

[1606003-20190612151920378-441349812.png]: /images/20211214/4dc6fe0b20784317a2acb352d26beedc.png
[1606003-20190612151940199-1627976925.png]: /images/20211214/51344434f61b4252a979f394b7368cda.png
[1606003-20190612152709952-1401161315.png]: /images/20211214/8b4f870d680c4cad99f4507c7cb10001.png