正常BFS题 但是数据很假
我写完看题解 发现有双向bfs做的 有KMP加快替换的
还有卡常的（大雾
于是心生一计 去复习了KMP 打算把两个放一起写
写完发现从原来的42ms -> 19ms
除了最前排的一堆人抄的unordered_map 或者 看不懂的科技 或者 对着答案数据预判直接continue的速度干不过
其他的而言还是很快的 把加强数据版本的过了 hzwer博客说的vijos上的会5个t也过了
总的来说还行 写太长就是折磨自己了
code
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <bits/stdc++.h>
using namespace std;
int n = 1;
string start, target;
string a[10], b[10];
set <string> s1, s2;
queue <pair<string, int>> q1, q2;
int nxt[2][10][30];
int main() {
s1.clear(); s2.clear();
cin >> start >> target;
start = '$'+ start, target = '$' + target;
while(cin >> a[n] >> b[n]) {a[n] = '$' + a[n]; b[n] = '$' + b[n]; n++;}
n--;
for (int i = 1; i <= n; i++) {
for (int j = 2, k = 0; j < a[i].size(); j++) {
while (k > 0 && a[i][j] != a[i][k+1]) k=nxt[0][i][k];
if (a[i][j] == a[i][k+1]) k++;
nxt[0][i][j] = k;
}
for (int j = 2, k = 0; j < b[i].size(); j++) {
while (k > 0 && b[i][j] != b[i][k+1]) k=nxt[1][i][k];
if (b[i][j] == b[i][k+1]) k++;
nxt[1][i][j] = k;
}
}
int step = 0;
q1.push({start, 0}), q2.push({target, 0});
while (++step <= 5) {
while (q1.front().second == step-1) {
string now = q1.front().first;
q1.pop();
for (int i = 1; i <= n; i++) {
string tem = now;
for (int j = 1, k = 0; j < tem.size(); j++) {
while (k > 0 && tem[j] != a[i][k+1]) k = nxt[0][i][k];
if (tem[j] == a[i][k+1]) k++;
if (k == a[i].size()-1) {
int pos=j - k + 1;
string res="$";
for (int z = 1; z < pos; z++) res += tem[z];
for (int z = 1; z < b[i].size(); z++) res += b[i][z];
for (int z = j + 1; z < tem.size(); z++) res+=tem[z];
if (s1.find(res) != s1.end()) {continue;}
if (s2.find(res) != s2.end()) {cout << step * 2 - 1 << endl; return 0;}
q1.push({res, step}); s1.insert(res);
}
}
}
}
while (q2.front().second == step-1) {
string now = q2.front().first;
q2.pop();
for (int i = 1; i <= n; i++) {
string tem = now;
for (int j = 1, k = 0; j < tem.size(); j++) {
while (k > 0 && tem[j] != b[i][k+1]) k = nxt[1][i][k];
if (tem[j] == b[i][k+1]) k++;
if (k == b[i].size()-1) {
int pos = j - k + 1;
string res="$";
for (int z = 1; z < pos; z++) res+=tem[z];
for (int z = 1; z < a[i].size(); z++) res+=a[i][z];
for (int z = j + 1; z < tem.size(); z++) res += tem[z];
if (s2.find(res) != s2.end()) {continue;}
if (s1.find(res) != s1.end()) {cout << step * 2 << endl; return 0;}
q2.push({res, step}); s2.insert(res);
}
}
}
}
}
cout << "NO ANSWER!";
return 0;
}
|