#include <bits/stdc++.h>
using namespace std;
signed main(){
int n; cin >> n;
string a, b; cin >> a >> b;
auto f = [&](string s){
int cnt = 0;
for ( auto &x: s ) cnt = cnt * 2 + x - '0';
return cnt;
};
int x = f(a), y = f(b);
vector <int> dp(1 << n, -1);
dp[x] = 0;
queue <int> q; q.push(x);
while ( !q.empty() ){
auto u = q.front();
q.pop();
for ( int i = 0; i < n; i++ ){
vector <int> nxt = {u, u ,u};
for ( int j = i; j < n; j++ ){
int b = u >> j & 1;
if ( b ) nxt[0] ^= 1 << j;
else nxt[1] ^= 1 << j;
nxt[2] ^= 1 << j;
for ( auto &v: nxt ){
if ( dp[v] == -1 ){
dp[v] = dp[u] + 1;
q.push(v);
}
}
}
}
}
cout << dp[y] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |