Ta đưa bài này về đồ thị như sau :

Nhận xét thấy, màu trên ô \((r,c)\) cho ta biết ràng buộc về màu của hàng \(r\) và cột \(c\).

• Nếu màu là 1-xanh lam hoặc 2-vàng : Hàng \(r\) và cột \(c\) có màu giống nhau, chính là màu ở ô \((r,c)\)
• Nếu màu là 3-xanh lục : Hàng \(r\) và cột \(c\) có màu khác nhau.

Ta coi mỗi hàng, mỗi cột như một đỉnh của đồ thị. Với mỗi ràng buộc : màu của đỉnh \(u\) khác màu của đỉnh \(v\), ta thêm cạnh \((u,v)\) vào đồ thị.

Ta tạo thêm 2 đỉnh ảo tượng trưng cho 2 màu xanh lam và vàng. Như vậy nếu đỉnh \(u\) có màu xanh lam thì ta thêm cạnh nối từ \(u\) tới vàng.

Sau khi thêm các cạnh vào đồ thị, ta sẽ thực hiện việc DFS từ đỉnh vàng và xanh rồi gán màu cho các đỉnh \(u\) gặp phải trong quá trình thăm. Nếu gặp mâu thuẫn : một đỉnh \(u\) được gán 2 màu khác nhau thì ta ngắt chương trình và in ra 0.

Những đỉnh không được nối với vàng và xanh tạo thành các TPLT, và chúng cũng cần được DFS qua để kiểm tra có mâu thuẫn hay không. Lưu ý, vì không được nối với màu cố định nên những đỉnh này có thể có 2 trạng thái màu, do đó nhân đôi kết quả (số lượng cấu hình bảng).

Có một số trường hợp đặc biệt trong bài này mà bạn cần phải chú ý :

• Input toàn 3
• Input toàn 0