You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
32 lines
810 B
C++
32 lines
810 B
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
int main() {
|
|
string S, T;
|
|
cin >> S >> T;
|
|
queue<string> Q;
|
|
map<string, int> M;
|
|
M[S] = 0;
|
|
Q.push(S);
|
|
for (; !Q.empty() && Q.front() != T; Q.pop()) {
|
|
string s = Q.front();
|
|
int step = M[s];
|
|
int pos = s.find('*'), st = max(pos - 3, 0), ed = min(pos + 4, (int) s.size());
|
|
for (size_t i = st; i < ed; i++)
|
|
if (i != pos) {
|
|
swap(s[i], s[pos]);
|
|
if (M.count(s) == 0) {
|
|
M[s] = step + 1;
|
|
Q.push(s);
|
|
}
|
|
swap(s[i], s[pos]);
|
|
}
|
|
}
|
|
cout << M[Q.front()];
|
|
return 0;
|
|
}
|