Trận chiến Hogwarts
Đề bài
Mô tả
Kẻ thù đang tiến vào Trường Phù thủy và Pháp sư Hogwarts. Hãy giúp Harry và các bạn bảo vệ ngôi trường!
Hogwarts có thể xem như một lưới gồm hàng và cột. Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ô ở hàng , cột được ký hiệu là .
Có loại ô:
- Tường: kẻ thù không thể đi vào các ô này.
- Bình thường: kẻ thù có thể đi vào các ô này. Harry có thể dùng phép thuật để chặn các ô này.
- Kháng phép: kẻ thù có thể đi vào các ô này, nhưng Harry không thể chặn chúng.
Kẻ thù tiến vào từ ô . Chúng có thể di chuyển giữa hai ô kề cạnh nhau. Tuy nhiên, chúng không thể đi vào ô tường hoặc ô bình thường đã bị Harry chặn.
Harry phải ngăn không cho kẻ thù đến được ô . Để làm điều đó, cậu có thể dùng phép thuật chặn một số ô bình thường. Lưu ý rằng nếu ô hoặc ô là tường hoặc bị Harry chặn, thì kẻ thù không thể đi từ ô đến ô .
Tuy nhiên, thời gian không còn nhiều! Harry cần biết số ô bình thường ít nhất cần chặn. Hãy giúp cậu ấy!
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa hai số nguyên dương và ().
- dòng tiếp theo, dòng thứ chứa đúng ký tự. Mỗi ký tự là một trong các ký tự sau:
#là ô tường;.là ô bình thường;@là ô kháng phép.
Dữ liệu vào kết thúc bằng hai số , và bạn không cần xử lý bộ dữ liệu này.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra đúng một dòng chứa số ô bình thường ít nhất Harry cần chặn để kẻ thù không đến được ô . Nếu không thể làm được, in ra .
Ràng buộc
- với mỗi bộ dữ liệu.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 @..# .... .... #..@ 4 4 @..# ..#. .#.. #..@ 0 0 |
2 0 |
Ở bộ dữ liệu thứ nhất, Harry có thể chặn ô và ; không thể chặn ô hoặc ít hơn mà vẫn ngăn được kẻ thù đến ô . Ở bộ dữ liệu thứ hai, các ô tường , , , đã chia cắt hai góc, nên không cần chặn ô nào. |
| 1 1 . 1 1 @ 1 1 # 1 3 @.@ 2 2 @@ @@ 0 0 |
1 -1 0 1 -1 |
Ví dụ bổ sung (không có trong đề gốc). Trong ba bộ đầu, ô cũng là ô : ô bình thường thì chặn nó, ô kháng phép thì không thể, ô tường thì không cần chặn gì. Với lưới , chặn ô giữa. Lưới cuối toàn ô kháng phép nên không thể. |
Bình luận