Lớp Biến Hình

Hướng tiếp cận

Bài toán yêu cầu tìm số phép biến hình ít nhất để biến bảng $A$ thành bảng $B$, trong đó mỗi phép biến hình chọn ô $(r,c)$ và đảo toàn bộ hình chữ nhật từ $(r,c)$ đến $(N,M)$. Lời giải dựa trên mảng sai phân XOR 2D.

Nhận xét quan trọng

1. Gộp hai bảng: Đặt $D[i][j]=A[i][j]\oplus B[i][j]$. Bài toán trở thành: tìm số phép ít nhất để biến $D$ thành toàn 0.

2. Mảng sai phân XOR 2D: Định nghĩa: $$d[i][j]=D[i][j]\oplus D[i-1][j]\oplus D[i][j-1]\oplus D[i-1][j-1]$$ (với $D[i][j]=0$ khi $i<1$ hoặc $j<1$). Mảng $d$ có tính chất: $D$ có thể được phục hồi từ $d$ bằng tiền tố XOR 2D.

3. Tác động của phép biến hình: Phép biến hình tại $(r,c)$ đảo tất cả $D[i][j]$ với $i\ge r,j\ge c$. Trong mảng sai phân, thao tác này chỉ thay đổi đúng 1 ô $d[r][c]$ (toggle giá trị tại đó), vì các thay đổi ở các ô khác triệt tiêu nhau.

4. Kết quả: Mỗi phép biến hình toggle đúng 1 ô trong $d$. Để đưa $D$ về toàn 0, ta cần $d$ cũng toàn 0. Vậy số phép tối thiểu bằng số ô có giá trị 1 trong mảng sai phân $d$.

Thuật toán

1. Đọc hai bảng $A$ và $B$.
2. Với mỗi ô $(i,j)$, tính: $$d[i][j]=(A[i][j]\oplus B[i][j])\oplus (A[i-1][j]\oplus B[i-1][j])\oplus (A[i][j-1]\oplus B[i][j-1])\oplus (A[i-1][j-1]\oplus B[i-1][j-1])$$
3. Đếm số ô có $d[i][j]=1$. Đó là đáp án.

Độ phức tạp

• Thời gian: $O(NM)$ - duyệt qua mỗi ô đúng 1 lần.
• Bộ nhớ: $O(NM)$ - lưu hai bảng $A$ và $B$.