题解 | #D、Word#

Sum

https://ac.nowcoder.com/acm/contest/38457/A

D、Word

前置知识：BFS（广度优先搜索）

问题解析

看到数据后我们发现，一共最多只有2000个字符串，字符串的最大长度才20，而且只有一个询问而已。那就可以先想暴力了，加上这里要求的是把s变成t的最少操作数，我们可以采用BFS的方法。

初始队列中存入字符串s。

在每一步的bfs中，我们可以枚举当前字符串的每一个位置，再在每个位置枚举a到z共26个字母，看修改过后的字符串是否有在那n个字符串出现即可，如果出现了，我们不妨把它变成这一个字符串，再把这个字符串存入队列中。直到这个字符串变成t为止。

根据BFS的性质，第一个变成字符串t的一定是最少次数。

题目还要求我们输出变化的路径，那我们可以在队列中，除了存下每一步的字符串，还存下这个字符串每次变换的过程，当这个字符串变成t后，我们把他们输出就行。

初始代码（未AC）：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6+50, MOD = 1e9+7;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    string s, t;
    unordered_map<string, int>mymap;
    vector<string>v(n + 1);
    for (int i = 1; i <= n; i++)
    {
    
        cin >> v[i];
        //把字符串都存入哈希表中
        mymap[v[i]] = i;
    }
    cin >> s >> t;
    //队列不仅要存当前的字符串，还要存它的变化过程
    queue<pair<string, vector<int>>>que;
    vector<int>res;
    que.push({ s,res });
    bool flag = false;
    while (!que.empty())
    {
        int len = que.size();
        for (int i = 0; i < len; i++)
        {
            auto tt = que.front();
            que.pop();
            string str = tt.first;
            //枚举每个位置
            for (int i = 0; i < m; i++)
            {
                string s2;
                //在这个位置上枚举a到z共26个字母
                for (char c = 'a'; c <= 'z'; c++)
                {
                    s2 = str;
                    s2[i] = c;
                    //如果这个字符串能直接变成t，那么我们就直接输出结果
                    if (s2 == t)
                    {
                        cout << tt.second.size() << endl;
                        cout << s << endl;
                        for (auto k : tt.second)
                        {
                            cout << v[k] << endl;
                        }
                        cout << t << endl;
                        return;
                    }
                    
                    //如果这个字符串出现在哈希表中
                    if (mymap.count(s2))
                    {
                        auto ttt = tt.second;
                        ttt.push_back(mymap[s2]);
                        
                        //我们把这个字符串和他变化的步骤都存入队列中
                        que.push({ s2,ttt });
                        
                    }
                }
            }
        }
    }
    cout << -1 << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

但是提交后就能发现，我们并不能ac题目，甚至一半的测试都没过。 alt

这是因为我们在bfs中会走很多重复的路径，比如字符串"qwq"变成"qwa"后，下一步"qwa"又变成"qwq"了，说实话，这样很蠢。

这里就要提到BFS/DFS中的灵魂操作——减枝。

我们在优先搜索的过程中会重复走很多之前走过的路，这样加大了我们的计算量，我们只要防止它再走回之前走过的路即可，这样就能减少我们的计算量。

对于这题来说，"qwa"变回"qwq"是因为"qwq"依然在我们的那n个字符串中，所以我们枚举的时候还会变回去。那么我们只要在枚举完“qwq”的所有变式后，把这个字符串从我们那n个字符串中删除即可。这样"qwa"就不会再变回"qwq"了。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6+50, MOD = 1e9+7;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    string s, t;
    unordered_map<string, int>mymap;
    vector<string>v(n + 1);
    for (int i = 1; i <= n; i++)
    {
    
        cin >> v[i];
        //把字符串都存入哈希表中
        mymap[v[i]] = i;
    }
    cin >> s >> t;
    //队列不仅要存当前的字符串，还要存它的变化过程
    queue<pair<string, vector<int>>>que;
    vector<int>res;
    que.push({ s,res });
    bool flag = false;
    while (!que.empty())
    {
        int len = que.size();
        for (int i = 0; i < len; i++)
        {
            auto tt = que.front();
            que.pop();
            string str = tt.first;
            //枚举每个位置
            for (int i = 0; i < m; i++)
            {
                string s2;
                //在这个位置上枚举a到z共26个字母
                for (char c = 'a'; c <= 'z'; c++)
                {
                    s2 = str;
                    s2[i] = c;
                    //如果这个字符串能直接变成t，那么我们就直接输出结果
                    if (s2 == t)
                    {
                        cout << tt.second.size() << endl;
                        cout << s << endl;
                        for (auto k : tt.second)
                        {
                            cout << v[k] << endl;
                        }
                        cout << t << endl;
                        return;
                    }
                    
                    //如果这个字符串出现在哈希表中
                    if (mymap.count(s2))
                    {
                        auto ttt = tt.second;
                        ttt.push_back(mymap[s2]);
                        
                        //我们把这个字符串和他变化的步骤都存入队列中
                        que.push({ s2,ttt });
                        
                        //减枝操作（就这短短一句代码哦）
                        mymap.erase(s2);
                    }
                }
            }
        }
    }
    cout << -1 << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

alt