Thuốc tẩy
Đề bài
Mô tả
Bé Khoai Tây Mìn đang làm việc trong một phòng thí nghiệm sinh học và gặp rắc rối lớn. Đĩa thí nghiệm chia ngăn của cậu là một khối hộp kích thước . Để tiện cho thí nghiệm, nó được chia thành khối lập phương đơn vị , và được dùng để chỉ một khối lập phương đơn vị.
Chiếc đĩa đã lâu không được sử dụng. Giờ Khoai Tây Mìn được yêu cầu làm sạch một số vùng của khối (mỗi vùng có thể được làm sạch nhiều lần). Cậu sẽ dùng một loại thuốc tẩy đặc biệt để làm sạch. Loại thuốc tẩy này rất kỳ lạ: mỗi lần làm sạch một vùng hình hộp chữ nhật kích thước (gồm khối đơn vị), lượng thuốc tẩy cần dùng là đơn vị. Thuốc tẩy không hề rẻ, điều này khiến Khoai Tây Mìn thấy không thoải mái. Hãy giúp cậu tìm lượng thuốc tẩy ít nhất cần dùng để làm sạch mọi khối đơn vị cần làm sạch.
Dữ liệu vào
Dòng đầu tiên chứa số bộ dữ liệu ().
Với mỗi bộ dữ liệu: dòng đầu tiên chứa số nguyên dương là kích thước của đĩa thí nghiệm ().
Tiếp theo là ma trận , mỗi ma trận gồm dòng, mỗi dòng số cách nhau bởi dấu cách, mô tả trạng thái của từng khối đơn vị ( nghĩa là khối đó không cần làm sạch, nghĩa là khối đó cần được làm sạch): số ở dòng thứ , cột thứ của ma trận thứ mô tả trạng thái của khối .
Dữ liệu ra
Với mỗi bộ dữ liệu, in trên một dòng lượng thuốc tẩy ít nhất cần dùng.
Ràng buộc
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 4 4 4 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 |
3 | Ví dụ của đề gốc. Làm sạch vùng tốn đơn vị và vùng tốn đơn vị thuốc tẩy. |
| 3 2 3 3 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 3 2 2 0 1 0 0 0 0 1 0 0 1 0 0 |
1 0 2 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: mọi ô cần làm sạch đều thuộc ma trận thứ nhất, làm sạch vùng tốn đơn vị. Bộ thứ hai: không có ô nào cần làm sạch. Bộ thứ ba: ba ô , , cần làm sạch; vùng và vùng tốn tổng cộng đơn vị. |
Bình luận