D - 美術館の巡回 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

ある美術館には、長さ N の白黒タイルの並びが展示された部屋がいくつかあります。各部屋の展示は長さ N の 01 文字列で表され、0 は白タイル、1 は黒タイルを意味します。ただし、同じ文字が 3 個以上連続して現れる文字列は美観上の理由で採用されておらず、そのような部屋は存在しません。

条件を満たすすべての文字列を辞書順で小さい順に並べ、先頭から順に部屋番号 1, 2, 3, \ldots を付けます。ただし、辞書順では 0 は 1 より小さいものとします。

2 つの部屋の展示がちょうど 1 箇所だけ異なるとき（すなわち、一方の文字列のある 1 文字を反転すると他方の文字列になるとき）、その 2 つの部屋は通路で直接つながっています。通路は双方向に通行でき、つながっている 2 部屋のどちらからでも他方へ移動できます。なお、1 文字を反転した結果が条件を満たさない（同じ文字が 3 個以上連続する）場合、その文字列に対応する部屋は存在しないため、通路もありません。

高橋君は、文字列 s に対応する部屋から巡回を開始します。出発した部屋は巡回開始の時点で訪問済みとなります。その後、次の操作を繰り返します。

  • 現在いる部屋に通路で直接つながっている未訪問の部屋が 1 つ以上存在するなら、その中で部屋番号が最も小さい部屋へ移動し、その部屋を訪問済みにする。
  • そのような部屋が存在しないなら、巡回を終了する。それ以前に通った部屋へ戻って探索を続けることはしない。

文字列 t に対応する部屋を初めて訪問するのが何回目の移動後かを求めてください。出発時点を 0 回目の移動後と数えます（s = t の場合は 0 を出力します）。文字列 t に対応する部屋を訪問しないまま巡回が終了する場合は -1 を出力してください。

制約

  • 1 \leq N \leq 26
  • s は長さ N の 0 と 1 からなる文字列である
  • t は長さ N の 0 と 1 からなる文字列である
  • s には同じ文字が 3 個以上連続して現れない
  • t には同じ文字が 3 個以上連続して現れない

入力

N
s
t
  • 1 行目には、タイルの並びの長さを表す整数 N が与えられる。
  • 2 行目には、出発する部屋に対応する文字列 s が与えられる。
  • 3 行目には、目標の部屋に対応する文字列 t が与えられる。

出力

文字列 t に対応する部屋を初めて訪問するのが何回目の移動後かを整数で出力せよ。訪問しない場合は -1 を出力せよ。

入力例 1

3
001
100

出力例 1

4

入力例 2

4
0010
1010

出力例 2

-1

入力例 3

12
010110010110
110100110100

出力例 3

-1

入力例 4

26
00110011001100110011001100
01010101010101010101010101

出力例 4

-1

入力例 5

1
0
0

出力例 5

0

Score : 400 pts

Problem Statement

A certain museum has several rooms, each displaying a sequence of black and white tiles of length N. The display in each room is represented by a binary string of length N, where 0 means a white tile and 1 means a black tile. However, strings in which the same character appears 3 or more times consecutively are not adopted for aesthetic reasons, and no such rooms exist.

All strings satisfying the condition are sorted in lexicographic order, and room numbers 1, 2, 3, \ldots are assigned from the beginning. In lexicographic order, 0 is considered smaller than 1.

When the displays of two rooms differ in exactly 1 position (that is, flipping one character of one string yields the other string), those two rooms are directly connected by a corridor. Corridors are bidirectional, and one can move from either of the two connected rooms to the other. Note that if flipping one character results in a string that does not satisfy the condition (the same character appears 3 or more times consecutively), the room corresponding to that string does not exist, so no corridor exists either.

Takahashi begins his tour from the room corresponding to string s. The starting room is considered visited at the beginning of the tour. After that, he repeats the following operation:

  • If there exists one or more unvisited rooms directly connected to the current room by a corridor, move to the room with the smallest room number among them, and mark that room as visited.
  • If no such room exists, end the tour. He does not backtrack to previously visited rooms to continue exploration.

Determine after how many moves the room corresponding to string t is first visited. The starting point counts as after 0 moves (if s = t, output 0). If the tour ends without visiting the room corresponding to string t, output -1.

Constraints

  • 1 \leq N \leq 26
  • s is a string of length N consisting of 0 and 1
  • t is a string of length N consisting of 0 and 1
  • s does not contain the same character appearing 3 or more times consecutively
  • t does not contain the same character appearing 3 or more times consecutively

Input

N
s
t
  • The first line contains an integer N representing the length of the tile sequence.
  • The second line contains the string s corresponding to the starting room.
  • The third line contains the string t corresponding to the target room.

Output

Output the number of moves after which the room corresponding to string t is first visited, as an integer. If it is not visited, output -1.

Sample Input 1

3
001
100

Sample Output 1

4

Sample Input 2

4
0010
1010

Sample Output 2

-1

Sample Input 3

12
010110010110
110100110100

Sample Output 3

-1

Sample Input 4

26
00110011001100110011001100
01010101010101010101010101

Sample Output 4

-1

Sample Input 5

1
0
0

Sample Output 5

0