Giả sử chúng ta có hai ma trận nhị phân N X M A và B. Trong một phép toán duy nhất, chúng ta có thể chọn một ma trận con (ít nhất là 2x2) và chuyển đổi tính chẵn lẻ của các phần tử góc (các bit lật). Cuối cùng, chúng ta phải kiểm tra xem ma trận A có thể được chuyển đổi thành B bằng cách thực hiện bất kỳ phép toán nào hay không.
Vì vậy, nếu đầu vào giống như
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
thì đầu ra sẽ là True vì chúng ta có thể thực hiện thao tác trên ma trận con hình vuông phía trên bên trái có kích thước (2x2) trên mat1 để nhận được mat2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- row:=số hàng của mat1
- column:=số cột của mat1
- đối với tôi trong phạm vi từ 1 đến hàng - 1, thực hiện
- đối với j trong phạm vi từ 1 đến cột - 1, thực hiện
- nếu mat1 [i, j] không giống với mat2 [i, j], thì
- 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
- nếu mat1 [i, j] không giống với mat2 [i, j], thì
- đối với j trong phạm vi từ 1 đến cột - 1, thực hiện
- đối với tôi trong phạm vi từ 0 đến hàng - 1, thực hiện
- đối với j trong phạm vi từ 0 đến cột - 1, thực hiện
- nếu mat1 [i, j] không giống với mat2 [i, j], thì
- trả về Sai
- nếu mat1 [i, j] không giống với mat2 [i, j], thì
- đối với j trong phạm vi từ 0 đến cột - 1, thực hiện
- trả về True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[ [1, 0, 0], [1, 0, 1], [1, 0, 0]], [ [0, 1, 0], [0, 1, 1], [1, 0, 0]]
Đầu ra
True