行列变换问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定2 个m×n方格阵列组成的图形A和B,每个方格的颜色为黑色或白色。行列变换问题的每一步变换可以交换任意2 行或2 列方格的颜色,或者将某行或某列颠倒。上述每次变换算作一步。试设计一个算法,计算最少需要多少步,才能将图形A变换为图形B。

对于给定的2 个方格阵列,计算将图形A变换为图形B的最少变换次数。

Input

输入数据的第1 行有2 个正整数m和n(m,n≤10)。以下的m行是方格阵列的初始状态A,每行有n 个数字表示该行方格的状态,0 表示白色,1 表示黑色。接着的m行是方格阵列的目标状态B。

Output

将计算出的最少变换次数和相应的变换序列输出。第1 行是最少变换次数,然后空一行。从第3 行开始,依次输出变换的图形序列,第一次是原图形序列,容纳后是变换的图形序列,每次变换的图形序列间用一个空行分开。问题无解时输出“No solution!”

Sample Input

4 4
1010
0100
0010
1010
1010
0000
0110
0101

Sample Output

2

1010
0100
0010
1010

1010
0000
0110
1010

1010
0000
0110
0101

Hint

 

Source