for (int i = 0; i < 3; i ++ ) // 更新每个操作后的新序列 { string s = get(t, i); if (!dist.count(s)) { dist[s] = dist[t] + 1; pre[s] = {'A' + i, t}; q.push(s); } } } }
intmain() { string start = "12348765", ans; for (int i = 1; i <= 8; i ++ ) cin >> a[i]; reverse(a + 5, a + 9); for (int i = 1; i <= 8; i ++ ) endd.push_back(a[i]);
cout << bfs() << '\n';
while (endd != start) { ans += pre[endd].first; endd = pre[endd].second; } reverse(ans.begin(), ans.end()); cout << ans; }
intextend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[N], string b[N])// 要处理da 从a->b { int d = da[q.front()]; while (q.size() && da[q.front()] == d) { auto t = q.front(); q.pop();
for (int i = 0; i < n; i ++ ) // 遍历每个规则 for (int j = 0; j < t.size(); j ++ ) // 遍历每个元素作为开头 if (t.substr(j, a[i].size()) == a[i]) { string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size()); // 记录新字符串 if (db.count(r)) return da[t] + db[r] + 1; // 在另一个里找到了,直接输出 if (da.count(r)) continue; // 在自己里找到了,说明重复了直接开始下一次循环 da[r] = da[t] + 1; // 更新距离 q.push(r); // 新字符串入队 } } return11; }
intbfs() { if (A == B) return0; queue<string> qa, qb; // qa qb两个队列同时搜索 unordered_map<string, int> da, db; // 不同字符串到起始字符串的步骤数
int step = 0; while (qa.size() && qb.size()) { int t; // 每次对队列长的那边进行操作 if (qa.size() < qb.size()) t = extend(qa, da, db, a, b); else t = extend(qb, db, da, b, a);
if (t <= 10) return t; if ( ++ step == 10) return-1; } return-1; }
intmain() { cin >> A >> B; while (cin >> a[n] >> b[n]) n ++ ;
int t = bfs(); if (t == -1) cout << "NO ANSWER!\n"; else cout << t << '\n'; }
typedef pair<int, string> PIS; #define ft first #define sd second
intf(string state)// 估价函数(曼哈顿距离) { int res = 0; for (int i = 0; i < state.size(); i ++ ) if (state[i] != 'x') { int t = state[i] - '1'; // 转换成数字 res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3); // 计算曼哈顿距离 } return res; }
cin >> n >> m; memset(h, -1, sizeof h); memset(rh, -1, sizeof rh);
for (int i = 0; i < m; i ++ ) { int a, b, c; cin >> a >> b >> c; add(h, a, b, c); // 存正向边 add(rh, b, a, c); // 存反向边(因为dijkstra里需要计算所有点到终点的最短路 } cin >> S >> T >> K; if (S == T) K ++ ;