第46届icpc 沈阳 J-Luggage Lock(思维 + 爆搜)
题目来源：第46届icpc 沈阳 J-Luggage Lock
题意：
给出两个四位数的密码锁a和b, 求由a变到b所需的最小步数
思路:
-
我们首先可以先将 a 变为 0000, 那么如果将 b 与 a 对应的位置旋转相同的次数, 那么 原始a -> 原始b 就等价于 0000 -> 修改后的b
- 比如 0003 -> 0005 可以转换成 0000 -> 0002, 1234 -> 4321 可以转换成 0000 -> 3197
-
我们记 c 为修改后的b, 那么此时我们就将 a -> b 转换成了 0000 -> c, 对于 c 我们会发现它最多有 10000 种状态, 所以此时我们可以直接爆搜
-
每次搜的时候将当前状态和从0000到当前状态所需的最小步数记录下来即可, 每次存储当前状态只用 1 步就能到达的状态.
那么怎么找当前状态只用一步就到的状态呢?
- 因为每次移动需要是连续的, 所以不难发现, 最多有20种情况, 我们存入一个string字符串中, '1’表示修改当前位, '0’表示不修改, 再加上向上和向下是一样的(传一个参数 1 或者 -1, 用来记录是向上还是向下), 所以我们只需要存一遍即可 : 1000, 0100, 0010, 0001, 1100, 0110, 0011, 1110, 0111, 1111
AC代码
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i, m, n) for (int i = (m); i <= (n); ++i)
#define rrep(i, m, n) for (int i = (m); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<string, int> PII;
const int N = 1e4 + 10, mod = 1e9 + 7;
int n, x[N]; // 记录 0000 到 i 需要的最小步数
bool vis[N]; // 记录状态是否访问过
string sss[] = { // 20种操作
"1000", "0100", "0010", "0001",
"1100", "0110", "0011", "1110",
"0111", "1111"
};
// 对状态s进行第idx种操作, c = 1 / -1, 记录是向上还是向下旋转
string change(string s, int idx, int c) {
string t = s;
for (int i = 0; i < 4; ++i)
if (sss[idx][i] == '1')
t[i] = (t[i] - '0' + c + 10) % 10 + '0';
return t;
}
void init() {
queue<PII> q; q.push({ "0000", 0 }); vis[0] = 1; // 推入起点
while (!q.empty()) {
auto t = q.front(); q.pop();
string s = t.first; int cnt = t.second;
for (int i = 0; i < 10; ++i) {
string p1 = change(s, i, 1);
string p2 = change(s, i, -1);
int a1 = stoi(p1), a2 = stoi(p2); // 字符串转换成数字
if (!vis[a1]) vis[a1] = 1, x[a1] = cnt + 1, q.push({ p1, cnt + 1 });
if (!vis[a2]) vis[a2] = 1, x[a2] = cnt + 1, q.push({ p2, cnt + 1 });
}
}
}
void solve() {
string a, b; cin >> a >> b;
string t = "0000";
for (int i = 0; i < 4; ++i)
t[i] = (b[i] - a[i] + 10) % 10 + '0';
printf("%d\n", x[stoi(t)]);
}
int main() {
init();
int t; cin >> t;
while (t--) solve();
return 0;
}