Python에서 부분행렬의 모서리 요소 패리티를 변경하여 행렬 A를 B로 변환할 수 있는지 확인

두 개의 N X M 이진 행렬 A와 B가 있다고 가정합니다. 단일 작업으로 부분 행렬(최소 2x2)을 선택하고 모서리 요소의 패리티(플립 비트)를 변환할 수 있습니다. 마지막으로 행렬 A가 여러 연산을 수행하여 B로 변환될 수 있는지 여부를 확인해야 합니다.

따라서 입력이 다음과 같으면

mat2를 얻기 위해 mat1에서 크기(2x2)의 왼쪽 위 정사각형 부분행렬에 대한 연산을 수행할 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• row :=mat1의 행 수
• column :=mat1의 열 개수
• 1~1행 범위의 i에 대해
  • 범위 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에 대해
    • mat1[i, j]가 mat2[i, j]와 같지 않으면
      • 거짓을 반환
• 참 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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