← 返回题目列表

AtCoder · awc0084_d

D. 博物馆巡逻

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

某个博物馆有几个房间,每个房间都展示一系列长度的黑白瓷砖 N。每个房间的显示都用一个长度的二进制字符串表示 N,其中 0 表示白色瓷砖,并且 1 表示黑色瓷砖。但是,出现相同字符的字符串 由于美观原因, 3 或连续多次不被采用,并且不存在这样的房间。

所有满足条件的字符串按照字典顺序排序,房间号 1, 2, 3, \ldots 从一开始就被分配。按照字典顺序, 0 被认为小于 1.

当两个房间的显示完全不同时 1 位置(即翻转一个字符串中的一个字符会产生另一个字符串),这两个房间通过走廊直接连接。走廊是双向的,一个人可以从两个相连的房间之一移动到另一个房间。请注意,如果翻转一个字符会导致字符串不满足条件(出现相同的字符) 3 或连续多次),该字符串对应的房间不存在,因此也不存在走廊。

高桥从弦对应的房间开始巡演 s。起始房间被视为在游览开始时访问过。之后,他重复以下操作:

  • 如果存在一个或多个通过走廊与当前房间直接相连的未访问过的房间,则移动到具有该房间的房间 最小房间号 其中 ,并将该房间标记为已访问。
  • 如果不存在这样的房间,则结束游览。他不会回到之前访问过的房间继续探索。

判断字符串对应的房间经过多少次移动 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
  • 第一行包含一个整数 N 表示图块序列的长度。
  • 第二行包含字符串 s 对应起始房间。
  • 第三行包含字符串 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