在一個(gè) 4×4 的棋盤上有8 個(gè)黑棋和 8 個(gè)白棋，當(dāng)且僅當(dāng)兩個(gè)格子有公共邊，這兩個(gè)格子上的棋是相鄰的。移動(dòng)棋子的規(guī)則是交換相鄰兩個(gè)棋子。

給出一個(gè)初始棋盤和一個(gè)最終棋盤，請找出一個(gè)最短的移動(dòng)序列使初始棋盤變?yōu)樽罱K棋盤。

前四行，每行 4 個(gè)數(shù)字（1 或者 0），描述了初始棋盤；

接著是一個(gè)空行；

第六到第九行，每行 4 個(gè)數(shù)字（1 或者 0），描述了最終棋盤。

1111
0000
1110
0010

1010
0101
1010
0101

4