VOI 16 Bài 4 - Trại bò tót

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI 2016 Day 2, task 4 - unofficial testdata
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ô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 ~m \times n~ ô 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_0,\: y_0)~ 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_0| + |y - y_0| \leq 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.

Input

  • 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.

Output

Đưa ra ~4~ số nguyên ~S, \:x_0,\: y_0, \: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_0,\: y_0~ 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ỳ.

Giới hạn

  • Có ~40~% số test ứng với ~40~% số điểm của bài có ~1 \leq m,\:n \leq 100.~
  • Có ~40~% số test khác ứng với ~40~% số điểm của bài có ~1 \leq m,\:n \leq 500.~
  • Có ~20~% số test còn lại ứng với ~20~% số điểm của bài có ~1 \leq m, \:n \leq 1000.~

Sample Input 1

2 3
...
..*

Sample Output 1

1 2 3 0

Sample Input 2

3 3
*.*
...
*.*

Sample Output 2

1 1 1 0

Sample Input 3

3 3
.*.
*.*
.*.

Sample Output 3

4 2 2 1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.