數據-連環鎖

連環鎖

Description

許多人一定很熟悉九連環（如下圖），九個環被串在一起，操作規則如下：第一個（右邊）環可以任意裝卸，如果第k個環沒有被卸掉，而第k個環前邊（右邊）的所有環都被卸掉，則第k+1個環（第k個環左邊的環）可以任意裝卸（如果存在的話）。
用0表示此換被卸掉，1表示此環沒有被卸掉，則九連環的每個狀態可以用一個長度為9的二進制串來表示，如：111111001經過一次操作可以變成111111000，也可以變成111111011，111111111經過一次操作可以變成111111110，也可以變成111111101。

任務描述：
你現在要操作的是一個n連環，n為正整數，給出n連環的兩種狀態，計算出從第一種狀態變換到第二種狀態所需要的最少步數。
Input

第一行是一個正整數m，表示有m組測試數據。
每組測試數據一共3行，第一行是一個正整數n (0 < n < 128)，後兩行每一行描述一種狀態，n個數（0或1），用空格隔開。
Output

對於每一組測試數據輸出一行，一個非負整數，表示從第一種狀態變換到第二種狀態所需要的最少步數。
Sample Input

2
3
0 0 0
1 0 0
4
1 0 0 0
0 1 1 0
Sample Output

7
11

最佳回答：

http://blog.csdn.net/AcmHonor/article/details/47055219