VM 15 Bài 01 - Đảo bit

View as PDF

Submit solution


Points: 0.48 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM15 - RR
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng kích thước ~M \times N~. Các hàng được đánh số từ ~1~ đến ~M~ từ trên xuống dưới. Các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. Mỗi ô của bảng có giá trị là ~0~ hoặc ~1~. Bạn được thực hiện thao tác: Chọn một hình vuông ~3 \times 3~ nằm trọn vẹn trong bảng và đảo bit tất cả các ô trong hình vuông đó (từ ~1~ chuyển về ~0~, hoặc từ ~0~ chuyển về ~1~). Mỗi hình vuông ~3 \times 3~ không được chọn quá một lần.

Nhiệm vụ của bạn là tìm một dãy ít thao tác nhất sao cho sau khi thực hiện thì bảng chỉ còn chứa số ~0~. In ra tọa độ ô trái trên của các hình vuông ~3 \times 3~ với tọa độ hàng tăng dần (nếu hai ô có cùng tọa độ hàng thì hình vuông nào có tọa độ cột của ô trái trên nhỏ hơn sẽ được in trước). Nếu không thể đưa bảng về toàn số ~0~ thì in ra ~-1~. Nếu có nhiều phương án, bạn có thể in ra phương án bất kỳ.

Input

  • Dòng ~1~: Chứa ~2~ số nguyên ~M~ và ~N~ (~M~, ~N \leq 100~).
  • ~M~ dòng tiếp theo: mỗi dòng chứa ~N~ số ~0~ hoặc ~1~.

Output

  • Dòng đầu chứa số ~K~ - số thao tác bạn thực hiện (nếu không tồn tại dãy thao tác thỏa mãn yêu cầu thì chỉ in ra duy nhất số ~-1~).
  • ~K~ dòng tiếp theo mô tả ~K~ thao tác được thực hiện, mỗi dòng chứa ~2~ số nguyên dương là tọa độ ô trái trên của các hình vuông ~3 \times 3~.

Giới hạn

  • Tất cả các test có ~M, N \leq 100~.
  • Trong ~40\%~ test (tương ứng với ~40\%~ số điểm), ~M \times N \leq 18~.

Sample Input

5 5
1 1 0 1 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0
0 1 1 1 0

Sample Output

3
1 1
1 3
3 2

Note

Ở test ví dụ này chỉ có ~1~ cách duy nhất thỏa mãn: Bạn cần đảo bit ~3~ hình vuông:

  • Hình có góc trên trái ở (~1~, ~1~)
  • Hình có góc trên trái ở (~1~, ~3~)
  • Hình có góc trên trái ở (~3~, ~2~)

Comments

Please read the guidelines before commenting.


There are no comments at the moment.