Devu and Perfume - CodeChef - JAN16

Devu and Perfume
Ở HauntedLand có một thị trấn ma ám. Cấu trúc của HauntedLand có thể xem như là một lưới kích thước n * m. Mỗi ô của lưới chứa một ngôi nhà. Một vài người đã chạy trốn khỏi ngôi nhà của mình vì họ đã nhìn thấy ma. ‘.’ đại diện cho một ngôi nhà bị ma ám còn ‘*’ đại diện cho một ngôi nhà đang có người ở. Một ngày, Devu, một người chế tạo nước hoa nổi tiếng đã tới thị trấn với một loại nước hoa mà mùi hương của nó có thể thôi miên người khác. Devu có thể để lọ nước hoa ở một căn nhà. Devu sẽ mất một giây để làm việc này. Sau đó, mùi hương sẽ lan từ một ngôi nhà tới những ngôi nhà kề đó trong một giây, và việc này cứ tiếp diễn. Một ngôi nhà được nói là kề với ngôi nhà khác nếu chúng có chung một đỉnh hay một cạnh.

Bạn muốn cứu mọi người khỏi Devu bằng cách gửi cho mọi người một cảnh báo để mọi người chạy ra khỏi thị trấn. Để làm được vậy, bạn cần phải biết thời gian tối thiểu để Devu thôi miên tất cả mọi người ?

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào là số nguyên T là số lượng bộ dữ liệu. Mô tả của T bộ dữ liệu như sau:
• Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên cách nhau bởi dầu cách n, m là kích thước của thị trấn.
• Trong n dòng tiếp theo, mỗi ngày sẽ chứa m ký tự (không có khoảng trắng) miêu tả một dãy ngang các ngôi nhà trong thị trấn.

Dữ liệu ra

• Với mỗi bộ dữ liệu, xuất ra một số nguyên tương ứng với kết quả cho bộ dữ liệu đó.
  Ràng buộc  1 ≤ T ≤ 20.
  Subtask #1: (40 điểm)  1 ≤ n, m ≤ 100
  Subtask #2: (60 điểm)  1 ≤ n, m ≤ 1000

Ví dụ
Dữ liệu vào:

2 
2 2 
*. 
.. 
3 3
.*. 
*** 
.*. 

Dữ liệu ra:

1 
2 

Giải thích

• Trong bộ dữ liệu đầu tiên, Devu sẽ cần một giây để đặt lọ nước hoa vào một ngôi nhà đang có người ở. Vì vậy nên câu trả lời là 1.
• Trong bộ dữ liệu thứ hai, anh ta sẽ đặt lọ nước hoa vào ô * ở giữa, ô (1, 1) (giả sử rằng tọa độ bắt đầu từ 0). Giờ, Devu sẽ tốn một giây để đặt lọ nước hoa. Ở giây thứ hai, mùi hương lan ra các ô kề với nó, vì vậy kết quả sẽ là 2.