檢查矩陣A是否可以透過更改Python中任何子矩陣的角元素的奇偶性轉換為B

假設我們有兩個N X M二進位制矩陣A和B。在單個操作中，我們可以選擇一個子矩陣（至少2x2），並轉換角元素的奇偶性（翻轉位）。最後，我們必須檢查是否可以透過執行任意數量的操作將矩陣A轉換為B。

因此，如果輸入如下所示：

則輸出為True，因為我們可以對mat1的左上角大小為(2x2)的子矩陣執行操作以獲得mat2。

為了解決這個問題，我們將遵循以下步驟：

• row := mat1的行數
• column := mat1的列數
• 對於 i 從 1 到 row - 1：
  • 對於 j 從 1 到 column - 1：
    • 如果 mat1[i, j] 與 mat2[i, j] 不相同，則：
      • mat1[i, j] := mat1[i, j] XOR 1
      • mat1[0, 0] := mat1[0, 0] XOR 1
      • mat1[0, j] := mat1[0, j] XOR 1
      • mat1[i, 0] := mat1[i, 0] XOR 1
• 對於 i 從 0 到 row - 1：
  • 對於 j 從 0 到 column - 1：
    • 如果 mat1[i, j] 與 mat2[i, j] 不相同，則：
      • 返回 False
• 返回 True

示例

讓我們看下面的實現來更好地理解：

 線上演示

def solve(mat1, mat2):
   row = len(mat1)
   column = len(mat1[0])
   for i in range(1, row):
      for j in range(1, column):
         if mat1[i][j] != mat2[i][j]:
            mat1[i][j] ^= 1
            mat1[0][0] ^= 1
            mat1[0][j] ^= 1
            mat1[i][0] ^= 1
   for i in range(row):
      for j in range(column):
         if mat1[i][j] != mat2[i][j]:
            return False
   return True
mat1 = [
         [1, 0, 0],
         [1, 0, 1],
         [1, 0, 0]]
mat2 = [
         [0, 1, 0],
         [0, 1, 1],
         [1, 0, 0]]
print(solve(mat1, mat2))

輸入

[
   [1, 0, 0],
   [1, 0, 1],
   [1, 0, 0]],
[
   [0, 1, 0],
   [0, 1, 1],
   [1, 0, 0]]

輸出

True

Arnab Chakraborty

更新於：2021年1月19日

163 次檢視

啟動您的職業生涯

完成課程獲得認證

開始