Pythonで部分行列の四隅の要素のパリティを反転して、行列AをBに変換できるかどうかを判定する方法

ここでは、2つの N × M のバイナリ行列 A と B が与えられているとします。1回の操作では、2×2 以上のサイズの部分行列を選択し、その四隅の要素のパリティ(0 と 1)を反転することができます。求めたいのは、この操作を任意の回数だけ繰り返して、行列 A を行列 B に変換できるかどうかの判定です。

たとえば、入力が次のような場合を考えてみましょう。

この場合の出力は True になります。mat1 の左上にある 2×2 の正方形部分行列に対して操作を1度実行すれば、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
• 処理後、すべてのセルを走査し、mat1[i][j] が mat2[i][j] と異なる箇所が1つでも残っていれば False を返します。
• すべて一致していれば True を返します。

なぜこの方法でうまくいくのか

(i, j)、(0, 0)、(0, j)、(i, 0) の4点を同時に反転するというのは、実質的に「行 0〜i、列 0〜j を範囲とする部分行列の四隅を反転する」という正当な操作そのものです。つまり、内側のセル(i ≥ 1、j ≥ 1)を左上から順に処理し、mat2 との差分があるたびに対応する操作を適用すれば、内側の領域は必ず mat2 と一致させられます。残るのは第0行と第0列のみなので、最後に行列全体を照合して判定すればよいわけです。

実装例(Python)

理解を深めるために、以下の実装を見てみましょう。

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

このアルゴリズムの計算量は、行列のサイズを R × C とした場合 O(R × C) です。各セルに対して操作は高々1回しか行われないため、大きな行列でも効率的に判定できるのが特徴です。