VMDAOBIT - Đảo bit

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho một bảng kích thước M * 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*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*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*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 N ( M, N ≤ 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*3 .

Giới hạn

  • Tất cả các test có M, N 100.
  • Trong 40% test (tương ứng với 40% số điểm), M*N 18.
  • Trong quá trình thi, bài của bạn chỉ được chấm với test ví dụ. Nếu được chấm đúng, kết quả sẽ được hiện là 100.

Ví dụ

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

Output:

3
1 1
1 3
3 2

Giải thích

Ở 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)


  • Người up: voj
  • Nguồn bài: VM15 - RR