結論から言うと、以下の愚直なシミュレーションすることでこの問題に正解できます。

• 各部屋を既に通ったかどうかのサイズ \(2^N\) の配列を保持する。
• 現在の部屋と先程の配列から、次に訪れる部屋を求めて移動する。
• 目標の部屋に到着するか手詰まりになれば終了する。

時間計算量が \(O(2^N N^2)\) となり、値を代入した際の額面が \(4.5 \times 10^{10}\) となり一見実行時間制限に間に合わなさそうですが、実はこの解法でも正答できます。

ポイント \(1\): 存在する部屋の総数の見積もり

実は、存在する部屋の総数は \(2^N\) よりも格段にに少ないです。

\(N=1\) では \(2\) 部屋、 \(N=2\) では \(4\) 部屋存在します。
\(N \ge 3\) では、同じ文字が \(3\) つ以上連続で存在しないという制約が効きます。
存在する部屋の数を見積もるために、以下を利用します。

• 全ての存在する部屋について、以下のルールでただ \(1\) 通りの方法で部屋番号を書くことができる。また、存在しない部屋の番号を書くこともない。
  • 0, 1, 00, 11 のどれかを選択して始める。
  • 現在の末尾の文字が 0 の時 1 を、 1 の時 0 を \(1\) 個または \(2\) 個末尾に連結することを繰り返す。

例えば部屋 100100 は、 1 から始めて 0 を \(2\) 個連結、 1 を \(1\) 個連結、 0 を \(2\) 個連結することで書くことができ、これ以外の方法はありません。

証明:
明らかに、同じ文字を \(3\) つ以上連続して書くことはないので存在しない部屋の番号を書くことはありません。
存在する部屋番号について、先頭を参照すると最初の 0, 1, 00, 11 の選択は一意に定まります。
また、末尾とは違う文字を \(1\) つか \(2\) つ末尾に繋げるという操作の性質上、同じ文字の連続は一度に繋げるしかないため、その後の操作も一意に定まります。

こうして、先述したルールで存在する全ての部屋番号をただ \(1\) 通りの方法で書くことができることが示されました。

長さ \(N\) の部屋の総数を \(f(N)\) とすると、 \(f(1)=2,f(2)=4\) であり、先ほどのルールより、 \(f(N)=f(N-1)+f(N-2)\) ( \(N \ge 3\) ) という漸化式で表現することができます。
この漸化式を前から計算していくと \(N=26\) について \(f(N)=392836\) です。
シミュレーションが高々 \(f(N)\) 回程度で停止することを考えると、先ほどの愚直なシミュレーションの時間計算量は \(O(2^N + f(N)N^2)\) とより良く見積もることができます。この額面は \(3.3 \times 10^8\) と、実行時間制限に辛うじて間に合いそうであることが分かります。

ポイント \(2\): 計算量から \(N\) をひとつ落とす

このポイントは必須ではありませんが、計算量改善ができるので紹介します。

存在する部屋から \(i\) 桁目を反転させる部屋移動を試すとき、 \(3\) 文字以上の連続が発生しうるのは以下の \(i\) 桁目が絡む場合のみです。

• \(i-2,i-1,i\) 文字目
• \(i-1,i,i+1\) 文字目
• \(i,i+1,i+2\) 文字目

このことを利用すると、長さ \(N\) の文字列全体を見なくとも部屋の存在判定ができます。

これを利用することで時間計算量 \(O(2^N + f(N)N)\) の解を得ることができ、額面計算量 \(7.7 \times 10^7\) の十分高速な解法を得ることができます(この額面の大部分は長さ \(2^N\) の配列を初期化するために使われているため、実際は高速です)。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int N;

int move(int tg,int x){
  int c=0;
  x^=(1<<tg);
  if(x&(1<<tg)){
    if(tg+1<N && (x&(1<<(tg+1)))>0){
      c++;
      if(tg+2<N && (x&(1<<(tg+2)))>0){
        c++;
      }
    }
    if(tg-1>=0 && (x&(1<<(tg-1)))>0){
      c++;
      if(tg-2>=0 && (x&(1<<(tg-2)))>0){
        c++;
      }
    }
  }
  else{
    if(tg+1<N && (x&(1<<(tg+1)))==0){
      c++;
      if(tg+2<N && (x&(1<<(tg+2)))==0){
        c++;
      }
    }
    if(tg-1>=0 && (x&(1<<(tg-1)))==0){
      c++;
      if(tg-2>=0 && (x&(1<<(tg-2)))==0){
        c++;
      }
    }
  }
  if(c>=2){return -1;}
  return x;
}
array<bool,1<<26> fl;

int main(){
  string s,t;
  cin >> N >> s >> t;
  int S=0,T=0;
  for(int i=0;i<N;i++){
    if(s[i]=='1'){S|=(1<<(N-1-i));}
    if(t[i]=='1'){T|=(1<<(N-1-i));}
  }
  fl[S]=1;
  for(int d=0;;d++){
    if(S==T){
      cout << d << "\n";
      return 0;
    }
    int nS=1e9;
    for(int dg=0;dg<N;dg++){
      int tg=move(dg,S);
      if(tg!=-1 && (!fl[tg])){
        nS=min(nS,tg);
      }
    }
    S=nS;
    if(S>5e8){
      cout << "-1\n";
      return 0;
    }
    fl[S]=1;
  }
  return 0;
}