【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 0000 \texttt{0000} 0000 to 0111 \texttt{0111} 0111 or 0900 \texttt{0900} 0900 in one step because the rotated digits are consecutive, but she can’t rotate 0000 \texttt{0000} 0000 to 0101 \texttt{0101} 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 a_0a_1a_2a_3 a0​a1​a2​a3​ and the password is b 0 b 1 b 2 b 3 b_0b_1b_2b_3 b0​b1​b2​b3​. 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 T T ( 1 ≤ T ≤ 1 0 5 ) (1 \leq T \leq 10^5) (1≤T≤105), 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 a_0a_1a_2a_3 a0​a1​a2​a3​ and the target state b 0 b 1 b 2 b 3 b_0b_1b_2b_3 b0​b1​b2​b3​.

输出格式

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 4 4位的密码，总共有 1 0 4 10^4 104种组合，因此，如果我们使用多源 b f s bfs bfs来寻找多源最短路，那么复杂度一定很大。

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

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

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

由于每次操作可以有 20 20 20次的变换，那么搜索的总的边数为 20 n 20n 20n，我们使用 s t d : : m a p std::map std::map来判重，最终时间复杂度在 O ( ( n + 20 n ) l o g 2 n ) O((n+20n)log_2n) O((n+20n)log2​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;
}