Đề khảo sát năng lực đội tuyển môn Tin học Năm 2020 - Trường THPT chuyên Bảo Lộc

Bài 2. Tô màu lưới

Cho lưới ô vuông kích thước m×n. Các hàng được đánh số từ 1 đến m, từ trên xuống dưới; các cột được đánh số từ 1 đến n, từ trái qua phải. Ô vuông thuộc hàng thứ i và cột thứ j có tọa độ (i, j). Người ta tô các ô vuông bởi 2×n màu có mã màu được đánh số từ 1 đến 2×n sao cho mỗi màu đều được tô cho ít nhất một ô. Ký hiệu Lj là số lượng màu khác nhau được sử dụng để tô các ô trong cột thứ j (j = 1, 2, …, n). Ta gọi độ đa sắc của lưới là giá trị . 

Cho phép thực hiện việc hoán đổi màu của hai ô ở hai đỉnh đối diện trên đường chéo của hình chữ nhật kích thước 2×3 bất kỳ (xem hình bên dưới). Mỗi phép hoán đổi được mô tả bởi bốn số nguyên (u, v, s, t) cho biết hai ô vuông (u, v) và (s, t) được hoán đổi màu. 

Ô đánh dấu bởi màu đen có thể hoán đổi màu với một trong các ô đánh dấu bởi màu xám 

Yêu cầu: Hãy xác định một dãy các phép hoán đổi màu để đưa lưới về trạng thái có độ đa sắc nhỏ nhất. 

Dữ liệu vào từ tệp văn bản CORLORTAB.INP gồm:

- Dòng thứ nhất chứa số nguyên dương T (T ≤ 30) là số lượng bộ dữ liệu. Mỗi nhóm dòng trong T nhóm dòng tiếp theo mô tả một bộ dữ liệu theo khuôn dạng sau: 

- Dòng đầu tiên chứa 2 số nguyên m, n (4 ≤ m, n ≤ 50) được ghi cách nhau bởi dấu cách; 

- Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên dương ci1, ci2, …, cin được ghi cách nhau bởi dấu cách, trong đó cij là mã màu của ô (i, j) trong lưới ban đầu (j = 1, 2, …, n). 

Kết quả được ghi ra tệp văn bản CORLORTAB.OUT:

Gồm T nhóm dòng, mỗi nhóm là kết quả tìm được cho bộ dữ liệu tương ứng trong dữ liệu vào, theo khuôn dạng sau: 

- Dòng đầu tiên ghi ra số nguyên không âm p là số lượng phép hoán đổi cần thực hiện;

- Tiếp đến là p dòng mô tả dãy các phép hoán đổi cần thực hiện để đưa lưới về trạng thái có độ đa sắc nhỏ nhất. Mỗi dòng ghi 4 số nguyên dương u, v, s, t cách nhau bởi dấu cách cho biết cần thực hiện việc hoán đổi màu của hai ô vuông (u, v) và (s, t).  Nếu có nhiều cách thực hiện để đưa lưới về trạng thái có độ đa sắc nhỏ nhất thì chỉ cần đưa ra một cách.