【ICPC】The 2021 ICPC Asia Shenyang Regional Contest J

Luggage Lock

#搜索 #枚举

题目描述

Eileen has a big luggage and she would pick a lot of things in the luggage every time when A-SOUL goes out for a show. However, if there are too many things in the luggage, the 4-digit password lock on the luggage will be hard to rotate.

The state of lock is the four digits on the lock. In one step, she can choose consecutive digits to rotate up by one simultaneously or down by one simultaneously. For example, she can rotate $\text{0000}$ to $\text{0111}$ or $\text{0900}$ in one step because the rotated digits are consecutive, but she can’t rotate $\text{0000}$ to $\text{0101}$ in one step. Since she has little strength, she wants to rotate the lock as few times as possible.

Now the lock is at state $a_0{a}_1{a}_2{a}_3$ and the password is $b_0{b}_1{b}_2{b}_3$. As a fan of A-SOUL, you are asked to help Eileen find out the optimal plan to unlock but you only need to tell Eileen how many times she has to rotate.

输入格式

The first line contains one integer $T$ $(1\le T\le 10^5)$, denoting the numer of test cases.

Each of the test cases contains a line containing the initial state $a_0{a}_1{a}_2{a}_3$ and the target state $b_0{b}_1{b}_2{b}_3$.

输出格式

For each test case, output a line containing a single integer, denoting the minimum steps needed to unlock.

样例 #1

样例输入 #1

6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468

样例输出 #1

1
1
4
5
1
4

解题思路

首先，对于只有$4$位的密码，总共有$10^4$种组合，因此，如果我们使用多源$bfs$来寻找多源最短路，那么复杂度一定很大。

考虑到每次操作都是等效的，因此我们可以利用相对位置的关系，将多源转为单源。

例如$1234->2267$，相当于$0000->1033$，因为相对距离固定，那么操作的最小次数一定也是固定的。

所以，我们只需要预处理出$0000$变为任何组合的最小操作次数即可。

由于每次操作可以有$20$次的变换，那么搜索的总的边数为$20n$，我们使用$std::map$来判重，最终时间复杂度在$O((n+20n)lo{g}_{2}n)$

代码

constexpr int dir[20][4] =
{ {1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},
{-1,0,0,0},{0,-1,0,0},{0,0,-1,0},{0,0,0,-1},
{1,1,0,0},{-1,-1,0,0},{0,-1,-1,0},{0,1,1,0},
{0,0,1,1},{0,0,-1,-1},{1,1,1,0},{-1,-1,-1,0},
{0,1,1,1},{0,-1,-1,-1},{1,1,1,1},{-1,-1,-1,-1} };std::map<std::string, int>mp;void bfs() {std::queue<std::pair<std::string, int>>q;q.push({ "0000",0 });mp["0000"] = 0;while (q.size()) {auto [s, dis] = q.front();q.pop();for (int i = 0; i < 20; ++i) {std::string t;for (int j = 0; j < 4; ++j) {t += (char)'0' + ((s[j] - '0') + dir[i][j] + 10) % 10;}if (!mp.count(t)) {q.push({ t,dis + 1 });mp[t] = dis + 1;}}}
}
void solve() {std::string s1, s2;std::cin >> s1 >> s2;std::string S;for (int i = 0; i < 4; ++i) {S += '0' + (s1[i] - s2[i] + 10) % 10;}int res = mp[S];std::cout << res << "\n";}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;bfs();while (t--) {solve();}return 0;
}