VO 14 Bài 5 - Trò chơi trên bảng

View as PDF

Submit solution

Points: 1.08 (partial)
Time limit: 1.2s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 14, RR
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 ~(R_{1}, C_{1})~ và ~(R_{2}, C_{2})~ mà ~R_{1} = R_{2}~ và ~C_{1} = C_{2}~ (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 \leq M, N \leq 5~
  • Trong ~60\%~ test còn lại, ~1 \leq M, N \leq 1000~

  • 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.

Sample Input

3 4
1000
0110
0000

Sample Output

3
1 1 1 3
1 1 2 1
1 1 2 3

Note

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.