c – 算法将一个硬币矩阵转移到另一个硬币矩阵

发布时间：2020-12-16 07:28:53 所属栏目：百科来源：网络整理

导读：描述： ?桌面上有m * n(m = 100,n = 100)个硬币,形成m行n列硬币矩阵.每枚硬币要么面朝上,要么面朝后,用0或1表示. 游戏规则是： (1)每次,你都可以反转一排硬币. ??(2)每次,你都可以交换两列. 宾语： ??从初始矩阵 – 目标矩阵输入： ???1. k测试的数量 ???2.

描述：
?桌面上有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

样本输出

-1

我编写了一个解决方案：mysolution.cc,它列举了所有可能性,哪些是正确的,但它太慢,你能提供正确但快速的解决方案.

谢谢.

解决方法

行总是保持在同一个位置,所以如果行r以k个开头,它将始终具有k个或列 – k.

>对于每一行,检查count_of_ones(初始,行)== count_of_ones(目标,行),如果是,罚款,否则检查count_of_ones(初始,行)=列 – count_of_ones(目标,则翻转row,否则输出-1.正如@maniek所指出的那样,只有一半的列包含那些列并不容易.必须在步骤2中处理这些行以尝试形成所需的列.>对于每列,计算目标和工作矩阵中的1的数量(在适当地翻转行之后).如果计数序列不是彼此的排列,则输出-1,否则尝试查找将工作转换为目标的列的排列(工作和目标之间相同的任何列必须保持固定).如果不可能,输出-1,否则找到实现该排列所需的最小交换次数.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!