Trò chơi khối hộp là một trò chơi với một khối hộp chữ nhật kích thước đơn vị trên lưới hình chữ nhật được chia thành ô vuong đơn vị. Các hàng của lưới được đánh số từ tới từ trên xuống dưới và các cột của lưới được đánh số từ tới từ trái qua phải. Ô nằm trên giao của hàng và cột được gọi là ô . Ban đầu khối hộp được đặt ở góc trái trên của lưới , cụ thể mặt đáy của khối hộp chứa đúng ô của lưới, là các ô nằm trong hình chữ nhật con của lưới với ô ở góc trái trên là và ô ở góc phải dưới là . Mỗi bước, người chơi có thể thực hiện một trong các loại thao tác sau:
Đẩy khối hộp tịnh tiến lên trên, xuống dưới, sang trái hoặc sang phải một ô;
Lật khối hộp tịnh tiến lên trên, xuống dưới, sang trái hoặc sang phải một ô.
Ví dụ: Các hình vẽ tronh Hình dưới đây mô tả vị trí của khối hộp kích thước sau khi thực hiện từng loại thao tác.
Hình 1
Khi bắt đầu trò chơi, tất cả các ô mà khối hộp đè lên được bật sáng màu xanh và có ô khác trên lưới được bật sáng màu đỏ, các ô còn lại ở trạng thái tắt. Một thao tác được gọi là hợp lệ, nếu sau khi thực hiện thao tác này, khối hộp vẫn nằm gọn trên lưới và không đè lên ô sáng màu đỏ nào. Sau khi một thao tác được thực hiện, những ô bị khối hộp đè lên đang ở trạng thái tắt sẽ được bật sáng màu xanh, những ô đang sáng màu xanh vẫn giữ nguyên trạng thái bật sáng màu xanh. Nhiện vụ của người chơi là tìm cách thực hiện dãy các thao tác hợp lệ để bật được nhiều ô sáng màu xanh nhất.
Yêu cầu: Cho khích thước khối hộp, kích thước của lưới và vị trí của các ô sáng màu đỏ, hãy xác định số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.
Dữ liệu vào:
Dòng thứ nhất chứa sáu số nguyên dương , các số được ghi cách nhau bởi dấu cách;
Dòng thứ trong số dòng tiếp theo chứa hai số nguyên dương được ghi cách nhau bởi dấu cách là tọa độ của một ô đã bật sáng màu đỏ .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.
Ví dụ:
Dữ liệu vào:
1 2 1 3 3 2
2 2
3 3
Dữ liệu ra:
7
Giải thích:
Hình vẽ trên mô tả trạng thái bắt đầu trò chơi, trong đó hai ô tô đen là các ô sáng màu đỏ. Người chơi có thể thực hiện thao tác: Lật sang phải, đẩy xuống dưới, đẩy lên trên, đẩy sang trái, đẩy sang trái, đẩy xuống dưới, đẩy xuống dưới, cuối cùng đẩy sang phải để bật được ô của lưới sáng màu xanh.
