1 条题解

  • 0
    @ 1 个月前
    #include <bits/stdc++.h>
    using namespace std;
    string A, B;
    int n;
    string a[25], b[25];
    map<string, int> dis;
    queue<string> q;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> A >> B;
        n = 1;
        while (cin >> a[n] >> b[n])
            n++;
        n--;
    
        dis[A] = 0;
        q.push(A);
        while (!q.empty())
        {
            string now = q.front();
            q.pop();
            for (int t = 1; t <= n; t++)
            {
                for (int i = 0; i + a[t].size() - 1 < now.size(); i++)
                {
                    bool flag = true;
                    for (int j = i; j < i + a[t].size(); j++)
                        if (now[j] != a[t][j - i])
                        {
                            flag = false;
                            break;
                        }
                    if (flag)
                    {
                        string nxt = "";
                        for (int j = 0; j < i; j++)
                            nxt += now[j];
                        nxt += b[t];
                        for (int j = i + a[t].size(); j < now.size(); j++)
                            nxt += now[j];
                        if (dis.find(nxt) == dis.end())
                        {
                            dis[nxt] = dis[now] + 1;
                            q.push(nxt);
                            if (nxt == B)
                            {
                                cout << dis[nxt] << "\n";
                                return 0;
                            }
                        }
                    }
                }
            }
        }
        cout << "NO ANSWER!";
        return 0;
    }
    
    • 1

    信息

    ID
    1762
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    100
    已通过
    12
    上传者