字串变换

发表于 更新于 分类于 阅读次数：

Luogu P1032 字串变换 还是bfs题，需要特别注意的是需要去重 因为是bfs，一旦找到合适的立马输出，即为最小值 实际上，使用std::string与std::set可以大大简化代码复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define rint register int
using namespace std;
int main() {
    string A, B, a[10], b[10], ta, tb;
    int tot;
    cin >> A >> B;
    while (cin >> ta >> tb) {
        a[tot] = ta;
        b[tot++] = tb;
    }
    queue<pair<string, int> > que;
    que.push(make_pair(A, 0));
    set<pair<string, int> > st;
    st.insert(make_pair(A, 0));
    while (!que.empty()) {
        pair<string, int> s = que.front();
        que.pop();
        if (s.first == B) {
            cout << s.second;
            return 0;
        }
        if (s.second == 10) continue;
        for (rint i = 0; i<tot; ++i) {
            string::size_type pos = 0;
            while ((pos = s.first.find(a[i], pos)) != string::npos) {
                string ss = s.first;
                ss.replace(pos, a[i].size(), b[i]);
                pair<string, int> p = make_pair(ss, s.second + 1);
                if (st.find(p) == st.end()) {
                    st.insert(p);
                    que.push(p);
                }
                pos += a[i].size();
                if (pos >= s.first.size()) break;
            }
        }
    }
    cout << "NO ANSWER!";
    return 0;
}