Phát hiện nguy hiểm
Đề bài
Mô tả
Một vùng đất được mô tả bởi lưới ô vuông kích thước . 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 gọi là ô . Qua khảo sát, mỗi ô có một sức chịu tải nhất định: ô có sức chịu tải là số nguyên dương .
Một robot xuất phát từ ô và cần đến ô , mỗi bước di chuyển sang một ô kề cạnh. Giả sử robot có trọng lượng ; khi đó một ô có sức chịu tải nhỏ hơn được coi là nguy hiểm. Mọi ô trên đường đi đều được tính, kể cả ô xuất phát và ô đích .
Nhiệm vụ của bạn là giải một trong hai bài toán sau:
- Cho trọng lượng của robot, tìm đường đi sao cho số ô nguy hiểm mà robot đi qua là ít nhất. In ra số ô nguy hiểm trên đường đi đó.
- Với lưới đã cho, tìm trọng lượng lớn nhất của robot sao cho nó có thể đến ô mà không đi qua ô nguy hiểm nào.
Dữ liệu vào
Dòng đầu tiên chứa số hoặc : bài toán cần giải.
Nếu dòng đầu tiên là , dòng thứ hai chứa hai số nguyên và . Nếu dòng đầu tiên là , dòng thứ hai chứa một số nguyên .
Dòng thứ trong dòng tiếp theo chứa số nguyên : hàng thứ của lưới.
Dữ liệu ra
In ra một số nguyên là kết quả của bài toán tương ứng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 5 6 7 1 3 4 6 6 2 1 7 5 2 6 7 2 3 4 2 1 1 7 9 1 6 1 6 |
3 | Đường đi qua các ô có sức chịu tải chỉ có ô nhỏ hơn (các ô , , ). |
| 2 5 7 1 3 4 6 6 2 1 7 5 2 6 7 2 3 4 2 1 1 7 9 1 6 1 6 |
2 | Từ ô và ô , mọi hướng đi tiếp đều phải qua một ô có sức chịu tải hoặc ; đường đi ở ví dụ trên có mọi ô . |
Bình luận