Pythonの任意の部分行列のコーナー要素のパリティを変更して、行列AをBに変換できるかどうかを確認します

2つのNXMバイナリ行列AとBがあるとします。1回の操作で、部分行列（少なくとも2x2）を選択し、コーナー要素（フリップビット）のパリティを変換できます。最後に、任意の数の操作を実行して行列AをBに変換できるかどうかを確認する必要があります。

したがって、入力が次のような場合

次に、mat1のサイズ（2x2）の左上の正方形のサブマトリックスで操作を実行してmat2を取得できるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• row：=mat1の行数
• column：=mat1の列数
• iの範囲が1から行-1の場合、実行します
  • 範囲1から列-1のjの場合、実行
    • 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
• 0から行-1の範囲のiの場合、実行
  • 範囲0から列-1のjの場合、do
    • 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