Theo dấu Bio-bot
Đề bài
Mô tả
Các nhà nghiên cứu ở công ty International Bio-bot Makers (IBM) đã phát minh ra một loại Bio-bot mới, một robot có hành vi mô phỏng sinh vật sống. Loại robot mới vẫn đang ở giai đoạn sơ khai; hiện nay chúng chỉ giống những chiếc xe tự hành bốn bánh đơn giản. Và giống như phần lớn robot hiện đại, Bio-bot không cơ động lắm. Động cơ yếu và khả năng rẽ hạn chế làm cho việc di chuyển của chúng bị giới hạn đáng kể, kể cả trong những môi trường đơn giản, gần như không có vật cản.
Hiện tại các Bio-bot hoạt động trong một căn phòng có thể mô tả bằng một lưới ( hàng, cột). Mỗi Bio-bot chiếm trọn một ô của lưới. Lối ra nằm ở góc đông bắc, và sàn phòng dốc xuống về phía đó, nên tại mọi thời điểm Bio-bot chỉ có thể di chuyển sang ô kề phía bắc hoặc phía đông. Một số ô trong phòng bị tường chiếm, tường chặn hoàn toàn robot. Hình dưới đây ứng với ví dụ thứ nhất (hàng trên cùng là hàng , cột trái nhất là cột ; # là tường).
grid .......E .###.... ........ ..#..... ........ ....#### ...A.... ........ label 1,8 lối ra highlight green 7,4 highlight red 7,5..8,8
Rõ ràng một Bio-bot đứng ở ô A (ô ) có thể rời khỏi phòng, còn một Bio-bot đứng ở ô B (ô , ngay bên phải A) thì bị kẹt trong phòng dù nó làm gì đi nữa. Những ô như B được gọi là "ô kẹt" (các ô tường không được tính là ô kẹt). Trong hình, 8 ô kẹt được tô đỏ. Cho mô tả của căn phòng, hãy đếm tổng số ô kẹt trong phòng.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, mỗi bộ test mô tả một căn phòng. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên , và (, ): căn phòng có hàng, cột và bức tường nằm ngang.
Mỗi dòng trong dòng tiếp theo chứa bốn số nguyên là tọa độ hai ô ở hai đầu của một bức tường; bức tường chiếm mọi ô với . Mọi bức tường đều nằm theo hướng tây sang đông, nên và . Các bức tường không chồng lên nhau.
Góc tây nam của phòng có tọa độ và góc đông bắc có tọa độ . Tọa độ nghĩa là cột và hàng ; đi về phía bắc làm tăng 1, đi về phía đông làm tăng 1.
Sau bộ test cuối cùng là một dòng chứa ba số 0.
Dữ liệu ra
Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test và số ô kẹt trong căn phòng đó, theo dạng Case i: x như trong ví dụ.
Ràng buộc
- , .
- , .
- Các bức tường không chồng lên nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 8 3 1 6 3 6 2 4 2 4 4 2 7 2 0 0 0 |
Case 1: 8 | Căn phòng trong hình: các ô kẹt là các ô có từ 4 đến 7 ở hai hàng và , nằm dưới bức tường đến . |
| 5 6 3 1 3 5 3 0 1 2 1 4 1 4 1 2 3 1 2 1 2 1 0 0 0 |
Case 1: 13 Case 2: 5 |
Phòng 1: hàng có 5 ô kẹt (, phía bắc là tường), hàng có 2 ô kẹt ( và ), cả 6 ô của hàng đều kẹt. Phòng 2: chính ô lối ra là tường nên cả 5 ô còn lại đều kẹt. |
Bình luận