描述:
桌面上有m*n(m<=100,n</100)个硬币形成m行n列的硬币矩阵。每枚硬币要么面朝上,要么面朝后,用0或1表示。
游戏规则是:
(1) 每次,你都可以反转一排硬币
(2) 每次都允许交换两列。
对象:
从初始矩阵->目标矩阵
输入:
1.k测试次数
2.m n行和列的计数
3.初始矩阵和目标矩阵的数目
输出从初始矩阵到目标矩阵的最小步长,如果不可能从初始矩阵转移到目标矩阵,则输出-1。
样本输入
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1
样本输出
2
-1
我已经编码了一个解决方案:mysolution.cc,它列举了所有的可能性,哪个是正确的,但太慢了,你能提供一个正确但快速的解决方案吗。
谢谢。
行始终位于同一位置,因此如果行r
以k
开始,则它将始终具有k
或columns - k
。
- 对于每一行,检查是否为
count_of_ones(initial,row) == count_of_ones(target,row)
,如果为,则为好,否则检查是否为count_of_ones(initial,row) = columns - count_of_ones(target,row)
,如果是,则翻转行,否则输出-1
。正如@maniek所指出的,当恰好有一半的列包含一个列时,这就不那么容易了。这样的行必须在步骤2中进行处理,以尝试形成所需的列 - 对于每一列,计算目标和工作矩阵中的1数(在适当地翻转行之后)。如果计数序列不是彼此的排列,则输出
-1
,否则尝试找到将工作转换为目标的列的排列(工作和目标之间相同的任何列都必须保持固定)。如果不可能,输出-1
,否则找到实现该排列所需的最小交换次数
我会给你一些想法。您可以逐行比较。如果第一个矩阵的第i行的数字与第二个矩阵的第一行的数字相同,则不求逆。如果第一个矩阵的第i行的数字1与第二个矩阵的第一行的数字0相同,则必须求逆。如果这两者都不是真的,那么就没有解决方案。这都是关于反演的。
现在,所有列都相等,但顺序不同(第二个矩阵从第一个矩阵排列了列)。如果列不是相互排列的,则返回-1。这个问题等于找到将一个排列转换为另一个排列的最小交换次数。