VOBOARD3 - Trò chơi trên bảng
Giới hạn- Thời gian: 0.8s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Tuy mới 10 tuổi, nhưng Bé đã rất thích chơi với các số nhị phân. Hàng ngày, Bé thường lấy 1 tấm bảng kích thước M*N và chơi một trò chơi như sau:
- Ban đầu, trên mỗi ô của bảng ghi một bit 0 hoặc 1.
- Mỗi nước đi, Bé chọn một vùng hình chữ nhật nằm hoàn toàn trong bảng, có các cạnh song song với các cạnh của bảng, và có kích thước R*C, và đảo bit tất cả các ô trong vùng đó.
- Mục tiêu của Bé là đưa tất cả các ô trên bảng về bit 0.
- Bé không thích sự lặp lại, vì thế Bé sẽ không bao giờ thực hiện 2 nước đi (R1, C1) và (R2, C2) mà R1 = R2 và C1 = C2 (Nói cách khác, Bé không bao giờ thực hiện 2 nước đi có cùng cả R và C).
Hôm nay Bé bị ốm, không thể chơi được. Bạn hãy giúp bé chơi trò chơi này nhé.
Các hàng của bảng được đánh số từ 1 đến M từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến N từ trái sang phải. Ô ở hàng i, cột j của bảng được kí hiệu là ô (i, j).
Input
- Dòng 1: Gồm 2 số nguyên dương M và N, là kích thước của bảng.
- M dòng tiếp theo, mỗi dòng gồm đúng N kí tự 0 hoặc 1, thể hiện trạng thái ban đầu của bảng.
Output
- Dòng 1: Gồm số nguyên dương Q duy nhất là số nước đi mà bạn thực hiện.
- Q dòng tiếp theo, mỗi dòng gồm đúng 4 số nguyên dương x, y, R, C thể hiện vùng mà bạn chọn, trong đó (x, y) là tọa độ ô trái trên của vùng được chọn, R và C là kích thước của vùng được chọn.
Giới hạn
- Trong 40% số test, 1 ≤ M, N ≤ 5
- Trong 60% test còn lại, 1 ≤ M, N ≤ 1000
Chấm điểm
- Bạn chỉ được điểm nếu dãy các nước di chuyển của bạn đưa bảng về gồm toàn bit 0.
Ví dụ
Input: 3 4 1000 0110 0000
Output: 2 1 1 1 1 2 2 1 2
Output sau KHÔNG hợp lệ (vùng kích thước 1*1 bị dùng 3 lần): 3 1 1 1 1 2 2 1 1 2 3 1 1
- Người up: voj
- Nguồn bài: VNOI Online 14, RR