用最小的行和列切换转化N×N的二元矩阵零矩阵矩阵、最小
这是有关我张贴关于将一种N×N的二元矩阵另一个问题。我问的问题是code-挑战的问题。然而，类似的问题被问在http://stackoverflow.com/questions/1310590/matrix-conversion.我通过线去，并且已经获得了有关如何去解决这个问题的一些想法。 我在这里重申这个问题。
This is about the question i posted regarding converting one NxN binary matrix to another . The question i asked is a code-challenge problem . However, a similar question was asked at http://stackoverflow.com/questions/1310590/matrix-conversion. I went through that thread,and have gained some idea about how to go about solving the problem. I restate the problem here.
我想写code，以解决以下问题。我打算用C，C ++，Java或Python的，这取决于两者可以更方便的解决方案。 给定两个N×N个（1＆其中; = N＆其中; = 2000）的二进制矩阵（每个A矩阵，其元素是一个1或0）中，A和B的问题是将阿为B，使用最少数量的允许操作。 允许的操作是： 1.我们可以切换成一排，＆NBSP;这将切换所有的值在该行，也就是说，它会改变1到0和0至1在该行中 2.我们可以切换列，＆NBSP;这将切换所有的值在该列中，也就是说，它会改变1到0和0至1在该列中。 如果没有解决方案很可能是我们打印-1
"I want to write code to solve the following problem. I am planning to use C, C++, Java or Python, depending on whichever allows a more convenient solution. Given two NxN (1 <= N <= 2000) binary matrices (A matrix each of whose element is either a one or a zero), A and B. The problem is to transform A into B, using the minimum number of permissible operations. The permissible operations are: 1. We can toggle a row, which will toggle all values in that row, i.e. it will change 1 to 0 and 0 to 1 in that row 2. We can toggle a column, which will toggle all values in that column, i.e. it will change 1 to 0 and 0 to 1 in that column. If no solution is possible we print -1"
不过，我有以下疑问的。
However, i have the following doubt.
予理解的是，在寻找转化A到B是计算阿XOR B .The 1的结果中的所需切换的最小数量的第一步骤是具有到被切换的地方，换句话说甲XOR B具有至转化为使用行和列切换的最小数目零矩阵。然而，它的我不清楚，如何甲XOR B为待转化到零矩阵，用行和列切换的最小数目。可能有人请一些线索呢？
I understood that the first step in finding the minimum number of toggles required to transform A to B is calculating A XOR B .The 1's in the result are the places which have to be toggled, in other words A XOR B has to be transformed to a zero matrix using the minimum number of row and column toggles . However, its not clear to me, how A XOR B is to be transformed to zero matrix , using the minimum number of row and column toggles. Could someone please shed some light on that ?
感谢你。
推荐答案
相当容易的事。
首先，我们应该明白，有开关一行或一列不止一次没有任何意义。为了更好地理解，我们国家表示这样的：每个单元具有0或1，并始终以总和的结果与模2：
First, we should understand that there is no sense in switching a row or a column more than once. For better understanding, we denote state like that: each cell has 0 or 1 in it and always take result of the sum with modulo 2:
final[i,j] = initial[i,j] + row_switched[i] + column_switched[j] (mod 2)
其中， row_switched 和 column_switched 是时候，我们交换第i行第j列数。现在，很明显，它们的值应该是0或1得到开关最小数量。
where row_switched and column_switched are numbers of times we switched i-th row and j-th column. Now it's clear, that their values should be 0 or 1 to get minimal number of switches.
但是，这实际上使...方程的系统！我们知道初始状态（假设），我们知道最终状态（零），我们只需要解决系统对研究[I] 和 C [ J] ！
But that actually makes... a system of equations! We know initial states (given), we know final states (zeros), we only need to solve the system against r[i] and c[j]!
不幸的是，它仍然是复杂的，因为模量来解决，并因为它不包括隐含的研究[I] 和ç[J限制] （即0或1）。
Unfortunately, it's still complex to solve because of moduli and because it doesn't include constraints implied on r[i] and c[j] (being 0 or 1).
让我们重新编写这些条件没有弹性模量：
Let's rewrite these condition without modulus:
row_switched[i] + column_switched[j] = 1 (if initial[i,j] = 1)
row_switched[i] - column_switched[j] = 0 (if initial[i,j] = 0)
已经写了这个对于每个小区，我们已经得到了N ^ 2方程的overdefined系统。让我们解决它在下面的方法。很明显，如果我们知道 row_switched [0] ，我们后来才知道整个的值 column_switched [] 阵列，因为他们清楚地由公式，其中 row_switched [0] 参与推断。然后，它很容易推断出每一行的价值。
Having written this for each cell, we have gotten an overdefined system of N^2 equations. Let's solve it in the following method. It's clear that if we knew the value of row_switched[0], we would then know the values of the whole column_switched[] array, because they're unambiguously deduced by the equations, in which row_switched[0] takes part. Then it's easy to deduce value of every row as well.
但是，我们只有两个变种 row_switched [0] ：0和1。让我们尝试他们每个人（参见下面的注释），并为每个，计算两个数组！那么，我们应该查看所有的方程式持有并选择两套一个满足的全系统并有较少开关
But we have only two variants for row_switched[0]: 0 and 1. Let's try each of them (SEE NOTE BELOW), and for each, calculate both arrays! Then we should check that all the equations hold and choose one of two sets that satisfies the whole system and has less switches.
如果没有满足它，然后，嗯，这是无法解决的。试图解决这一个，嘿：
If neither satisfies it, then, well, it's unsolvable. Try to solve this one, heh:
0 1
0 0
这完成了解决方案。我希望你做一个+1只是为了尝试。 ：）
This completes the solution. I hope you'll do a +1 just for trying. :)
在谈到为什么这是开关的最小可能数。事实上，任何的有效的的开关应当满足上述方程系统（具有0和1作为约束值）数目。但是，系统有不超过两个解决方案，和我们发现他们都高于的算法研究。所以，上述一定的算法找到的最小之一。
On the question why this is the least possible number of switches. Indeed, any valid number of switches should satisfy the system of equations outlined above (with 0 and 1 as constraints for values). But that system has not more than two solutions, and we find them all in the algorithm above. So, the algorithm above surely finds the minimal one.
注意： 它的似乎的给我，我们只能尽量集合中的一个。如果一个通过了系统，其他应该通过为好。一组是另一个的否定，所以我们只选择了一组用更少的交换机数量。开关总和为2N。但这只是的似乎的，并且比其它的部分不太清楚。
NOTE: It seems to me, that we can only try one of set. If one passes the system, the other should pass as well. One set is a negation of another, so we just choose the set with less switch number. Sum of switches is 2N. But this only seems and is less clear than the other part.
