Giải bài trực tuyến

Ông Bảo là chủ của một trang trại, đang nuôi một đàn bò 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 của 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ý 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. Thửa đất hình thoi có tâm tại ô (x₀, y₀) và bán kính là r là tập hợp tất cả các ô có tọa độ (x, y) thỏa mãn |x – x₀| + |y – y₀| <= r. 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.

Yêu cầu: Giúp Hùng xác định thửa đất có dạng hình thoi nằm trọng vẹn trong khu đất với số cọc cột bò là nhiều nhất đáp ứng yêu cầu của ông Bảo.

Dữ liệu:

-        Dòng đầu tiên chứa 2 số nguyên m và n xác định kích thước của khu đất của ông Bảo.

-        Dòng  thứ i trong m dòng sau chứa n kí tự liền nhau, mỗi kí tự xác định trạng thái của một thửa đất: ‘*’ nếu ô đất có cắm cọc và ‘.’ nếu ô đất đó không cắm cọc.

Kết quả: Đưa ra 4 số nguyên S, x₀, y₀, r được ghi cách nhau một dấu cách, trong đó: S là tổng số cọc trong thửa đất được chọn; x₀, y₀ là tọa độ tâm và r là bán kính của thửa đất đó. Nếu có nhiều lời giải hãy đưa ra một lời giải bất kỳ.

Ví dụ:

Ràng buộc:

-        Có 40% số test ứng với 40% số điểm của bài có 1 <= m,n <= 100

-        Có 40% số test khác ứng với 40% số điểm của bài có 1 <= m,n <= 500

-        Có 20% số test còn lại ứng với 20% số điểm của bài có 1 <= m,n <= 1000