Bom
Đề bài
Mô tả
Alice đang chơi một trò chơi khác tên là BOOM. Trò chơi có một bản đồ hình chữ nhật kích thước . Mỗi ô là một bức tường, một kẻ địch hoặc một ô trống. Trong trò chơi này, một quả bom có tầm nổ theo phương ngang với bán kính . Nói cách khác, nếu bom được đặt ở ô thì tầm nổ của nó là từ ô đến ô . Không được đặt bom ở ô tường, được phép đặt bom ở các ô còn lại. Bom nổ tại ô được đặt và lan sang hai bên theo phương ngang cho đến khi hết tầm nổ hoặc gặp tường. Lưu ý tường không bị bom phá hủy.
Trong trò chơi này, Alice sẽ mang theo đúng quả bom. Vì vậy, trước khi vào bản đồ, Alice phải mua quả bom có cùng tầm nổ . Để tiết kiệm tiền trong trò chơi, Alice sẽ mua đúng quả bom với nhỏ nhất mà vẫn tiêu diệt được tất cả kẻ địch trên bản đồ (Alice không nhất thiết phải dùng hết quả bom).
Hãy giúp Alice tính nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên dương (, ).
- dòng tiếp theo, mỗi dòng chứa ký tự thuộc các loại sau:
#là tường,.là ô trống,xlà kẻ địch.
Dữ liệu ra
In ra nhỏ nhất để Alice có thể đặt quả bom tiêu diệt tất cả kẻ địch. Nếu không có đáp án, in ra .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 6 5 #x..#. #.x.x# ..#.xx x....x |
1 | Với , Alice có thể đặt quả bom ở các ô , , , , . Đây là nhỏ nhất. |
| 2 3 10 xxx xxx |
0 | Alice có thể đặt bom ở tất cả các ô của bản đồ. |
| 2 2 1 x. x. |
-1 | Alice không thể tiêu diệt tất cả kẻ địch chỉ với quả bom. |
Bình luận