通过翻转1的矩阵的行和列来确定是否可以到达给定二进制矩阵的算法

Question

我需要帮助找到一个尽可能有效的算法来检查是否可以通过仅用一个矩阵翻转矩阵的行和列来达到给定的二进制矩阵.每当你翻转一行或一个col时,0变为1,所有1变为0

通过翻转1的矩阵的行和列来确定是否可以到达给定二进制矩阵的算法

例如,可以通过翻转第二行然后翻转第二列来达到此矩阵:

+---+---+---+
| 1 | 0 | 1 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 1 | 0 | 1 |
+---+---+---+

但这个矩阵不可​​能是你做的任何翻转

+---+---+---+
| 1 | 0 | 0 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 0 | 0 | 1 |
+---+---+---+

Answer 1

这可以测试如下:

取目标矩阵的第一列.所有其他列应该与第一列相同,或者应该相反(翻转).如果且仅当这种情况发生时,则可以通过来自具有全1值的初始矩阵的行/列的翻转来到达目标矩阵.

您也可以使用行进行测试,但只需使用行或列执行测试即可.

哪个翻转？

如果上述测试结果为正,您还可以查看可以执行哪些翻转以达到目标矩阵:

在目标矩阵的第一行中,标识值为0的单元格:这些是您需要在初始矩阵中翻转的列.

在目标矩阵的第一列中,标识具有与目标矩阵左上角中的值不同的值的单元格(因此这已经排除了第一个值):这些是您需要在初始值中翻转的行矩阵.

翻转的顺序并不重要.显然,这只提供了一个解决方案.一般来说可以有不止一个.

履行

这是一个简单的JavaScript代码段,可执行验证并提供可交换的列和行列表:

function getFlips(matrix) {
    // Verification
    for (let i = 1; i < matrix.length; i++) {
        let flip = matrix[i][0] ^ matrix[0][0]; // XOR operation
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] ^ flip != matrix[0][j]) return false; // Not possible
        }
    }
    // If we get here, it is possible: determine which rows/columns to flip
    let flips = { rows: [], columns: [] };
    for (let j = 0; j < matrix[0].length; j++) {
        if (matrix[0][j] == 0) flips.columns.push(j+1);
    }
    for (let i = 1; i < matrix.length; i++) {
        if (matrix[i][0] != matrix[0][0]) flips.rows.push(i+1);
    }
    return flips;
}


// I/O management
inp.oninput = function () {
    // Convert input to matrix of numbers
    let matrix = inp.value.split('\n').map(row => Array.from(row, Number));
    // Perform algorithm
    let flips = getFlips(matrix);
    // Output the result in human readable format
    out.textContent = flips 
        ? 'Number(s) of the column(s) to flip: ' 
            + (flips.columns.length ? flips.columns : 'none') + '\n' +
          'Number(s) of the row(s) to flip: ' 
            + (flips.rows.length ? flips.rows : 'none')
        : 'Not possible';
};

inp.oninput();

Enter the values of the matrix:<br>
<textarea id="inp" rows="4" cols="4">101
010
101</textarea><br>
Solution:
<pre id="out"></pre>