Đặt cược an toàn
Đề bài
Mô tả
Công ty Safe Ltd. sản xuất két sắt chất lượng cao. Phát minh mới nhất của công ty là một cơ chế khóa quang học: một tia laser đi qua một lưới hình chữ nhật có đặt một số tấm gương.

Hình trái: tia được phát hiện, két mở. Hình phải: tia không được phát hiện, chuông báo động kêu.
Khi bật laser, tia sáng đi vào hàng trên cùng của lưới theo phương ngang từ bên trái. Tia bị phản xạ bởi mọi tấm gương mà nó gặp. Mỗi tấm gương đặt chéo độ, theo một trong hai hướng / hoặc \. Nếu tia ra khỏi hàng dưới cùng của lưới theo phương ngang về bên phải thì tia được phát hiện và két mở (xem hình bên trái). Ngược lại két vẫn đóng và chuông báo động kêu.
Mỗi két sắt bị thiếu một tấm gương, khiến tia laser không đi qua lưới thành công được (xem hình bên phải). Két có một cơ chế cho phép người dùng thả đúng một tấm gương vào một ô trống bất kỳ của lưới. Người dùng hợp lệ biết vị trí và hướng đúng của tấm gương còn thiếu (ở hình trên là gương / tại hàng , cột ) nên mở được két. Không biết điều này thì người dùng phải đoán đúng, việc này có thể rất khó với các két có lưới lớn.
Nhiệm vụ của bạn là xác định một số két sắt có thực sự an toàn hay không. Một két an toàn là két không tự mở khi chưa thả gương, và có ít nhất một vị trí cùng hướng hợp lệ cho tấm gương còn thiếu. Thực tế có thể có nhiều vị trí và hướng như vậy.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test mô tả một két sắt, bắt đầu bằng một dòng gồm bốn số nguyên , , và ( và ). Lưới của cơ chế khóa có hàng và cột. Hàng được đánh số từ tới từ trên xuống, cột được đánh số từ tới từ trái sang.
Mỗi dòng trong dòng tiếp theo gồm hai số nguyên và ( và ), cho biết có một gương / ở hàng , cột . dòng tiếp theo cho vị trí các gương \ theo cùng cách. vị trí gương đôi một khác nhau.
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test theo định dạng trong ví dụ, tiếp theo là:
0nếu két mở mà không cần thả gương.k r cnếu két không mở khi chưa thả gương, có đúng vị trí mà thả một gương vào đó thì két mở, và là vị trí (hàng, cột) nhỏ nhất theo thứ tự từ điển trong các vị trí đó. Một vị trí mà cả gương/lẫn gương\đều mở được két chỉ được tính một lần.impossiblenếu không thể mở két, dù có thả gương hay không.
Ràng buộc
- .
- .
- , ; các vị trí gương đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 1 4 2 3 1 2 2 5 4 2 5 5 100 100 0 2 1 77 100 77 100 100 0 0 |
Case 1: 2 4 3 Case 2: 0 Case 3: impossible |
Bộ 1 là két ở hình phải: tia đi xuống ở cột rồi ra khỏi lưới ở bên phải hàng . Thả gương / vào ô (hình trái) hoặc gương \ vào ô (tia rẽ xuống, gặp gương ở ô rồi ra bên phải hàng ) đều mở được két, nhỏ nhất là . Bộ 2: tia gặp gương \ ở ô , đi xuống tới gương \ ở ô rồi ra bên phải hàng , két tự mở. Bộ 3: không có gương, tia đi thẳng ra bên phải hàng ; thả một gương thì tia rẽ đúng một lần (lên hoặc xuống) rồi ra khỏi lưới ở mép trên hoặc mép dưới, không thể ra bên phải hàng . |
| 3 5 0 3 1 3 3 2 2 4 |
Case 1: 2 1 2 | Ba gương đều là \. Chưa thả gương thì tia gặp gương ở ô , đi xuống cột rồi ra khỏi đáy lưới. Thả gương \ vào ô thì tia đi xuống cột , gặp gương ở ô và ra bên phải hàng . Thả gương \ vào ô cũng làm tia rẽ sang phải ở hàng . Có vị trí, nhỏ nhất là . |
Bình luận