Bàn cờ

HSG Hà Nội lớp 12 năm 2010-2011, bài 3/3
Cho một bàn cờ kích thước m x n ô, các dò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. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j) và khi đó, i được gọi là chỉ số còn j được gọi là chỉ số cột của ô này. Được phép đặt một quân vua vào một ô của bàn cờ (mỗi ô đặt không quá một quân), khi đó nó có thể khống chế 8 ô lân cận xung quanh (8 ô được đánh số từ 1 đến 8, xem hình vẽ dưới đây).
     1 2 3
     8 x 4 (x là quân hậu)
     7 6 5
Trên bàn cờ đã đặt trước một số quân vua (không có 2 quân nào khống chế nhau), người ta muốn đặt thêm nhiều nhất các quân vua lên bàn cờ mà vẫn đảm bảo không có 2 quân vua nào khống chế nhau.
Yêu cầu: Cho biết các ô đã đặt quân vua, hãy đặt thêm nhiều nhất quân vua lên bàn cờ sao cho trên bàn cờ không có 2 quân nào khống chế nhau.
Dữ liệu: Vào từ file văn bản Bai3.INP có dạng
   - Dòng đầu tiên chứa 3 số nguyên m,n,k (0<m , n < 30; 0 <=k<=m mx n). Trong đó m,n là kích thước bàn cờ, k là số quân vua đã được đặt trên bàn cờ.
   - Dòng thứ i trong k dòng tiếp theo gồm 2 số ai ,bi là chỉ số dòng và chỉ số cột của ô thứ i đã có quân vua.
Kết quả: Ghi ra file văn bản Bai3.OUT có dạng:
   - Dòng đầu tiên ghi số nguyên s là số lượng nhiều nhất quân vua được đặt thêm lên bàn cờ.
   - Dòng thứ i trong s dòng tiếp theo gồm 2 số xi, yi là chỉ số dòng và chỉ số cột của quân vua thứ i được đặt thêm lên bàn cờ (nếu có nhiều phương án đưa ra một phương án bất kỳ).
Ví dụ 1:
   Bai3.INP                 Bai3.OUT
     2 3 0                        2
                                     1 1
                                     2 3
Ví dụ 2:
   Bai3.INP                 Bai3.OUT
     3 3 1                        0
     2 2

                                                           Lời giải tham khảo