1 条题解
-
3
#include<bits/stdc++.h> using namespace std; struct node { string _Str; int _Tot; }; unordered_map<string, bool> mp; string a, b; string A(string S, int x) { string s = S; if (s[x] == '9') s[x] = '1'; else s[x] ++; return s; } string B(string S, int x) { string s = S; if (s[x] == '1') s[x] = '9'; else s[x] --; return s; } void bfs() { std::queue<node> q; q.push((node) { a, 0 }); while (!q.empty()) { node now = q.front(); string s = now._Str; int tot = now._Tot; q.pop(); if (s == b) { printf("%d", tot); return; } tot ++; for (int i = 0; i < 3; i ++) { string cnt = s; swap(cnt[i], cnt[i + 1]); if (!mp[cnt]) q.push((node) { cnt, tot }), mp[cnt] = true; } for (int i = 0; i < 4; i ++) { string cnt = A(s, i); if (!mp[cnt]) q.push((node) { cnt, tot }), mp[cnt] = true; cnt = B(s, i); if (!mp[cnt]) q.push((node) { cnt, tot }), mp[cnt] = true; } } } int main() { freopen("lock.in", "r", stdin); freopen("lock.out", "w", stdout); cin >> a >> b; bfs(); return 0; }
信息
- ID
- 560
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 60
- 已通过
- 12
- 上传者