E. mm逗黑白猫

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

mm在渡渡鸟幼儿园发现一堆黑白猫玩具,mm可是很仰慕围棋大佬,于是决定把它们摆在棋盘上当围棋(并不)玩耍。

黑白猫盘由一个 的方格构成,棋盘的每一方格中放有 只猫,共有 只白猫和 只黑猫。在棋盘上拥有1条公共边的2个方格称为相邻方格。在玩黑白猫游戏时,每一步可将任何2个相邻方格中猫互换位置。mm要做的就是通过多次互换位置把给定的初始猫排列状态变成目标猫排列状态。

输入格式

输入文件共有 行。前 行是初始猫排列状态,后 行是目标猫排列状态。

每行有 个数字0或1(无空格),分别表示该行放置的猫颜色,其中 表示白猫, 表示黑猫。

输出格式

第一行输出互换步数

接下来 行,每行 个正整数(无空格),分别表示该步交换的两个相邻方格的位置。例如, 表示将棋盘上 处的猫与 处的猫换位。

注意,如果有多种合法方案,你的方案需要保证:

  1. 所需步数最小。

  2. 输出时保证

  3. 在满足以上两个条件的前提下,输出字典序最小的方案。

样例

样例输入

1111
0000
1110
0010
1010
0101
1010
0101

样例输出

4
1222
1424
3242
4344