Kỳ thi chọn học sinh giỏi Quốc gia THPT môn Tin học vòng 2 - Năm học 2016-2017

Bài 4. Trại bò tót (6 điểm)

Ông Bảo là chủ của một trang trại, đang nuôi một đàn bò tót trên khu đất hình chữ nhật chia thành lưới mxn ô vuông đơn vị. Các hàng của lưới được đánh số từ 1 tới m từ trên xuống và các cột của lưới được đánh số từ 1 tới n từ trái qua phải. Ô nằm trên giao điểm của hàng i và cột j được gọi là ô (i, j). Tại tâm một số ô đã cắm cọc, mỗi cọc để buộc một con bò. Để bảo vệ đàn bò tót quý giá của mình khỏi những tên trộm, ông Bảo thuê Hùng tìm một thửa đất có dạng hình thoi (mà theo quan niệm của ông Bảo là biểu tượng cho may mắn) trong khu đất để nhốt đàn bò của mình. Một thửa đất hình thoi có tâm tại ô (xo, yo) và bán kính r là tập hợp tất cả các ô có tọa độ (x, y) thỏa mãn: |x − xo| + |y − Yo| ≤ r (xem Hình 1). Do bò tót là các con vật rất hung dữ, nên ông Bảo yêu cầu trong thửa đất tìm được không có hai ô có cọc nào lại có cạnh chung.