Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMDAOBIT - Đảo bit

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmdaobit


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 MN (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)

Được gửi lên bởi:VOJ Team
Ngày:2015-07-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM15 - RR

hide comments
2020-02-25 14:35:34
đọc qua tưởng khó mà dễ và đơn giản đến ngạc nhiên -_-
2019-11-05 14:44:53
Sử dụng định lý 0 = 2 và 1 = 3 là AC
2017-08-10 19:30:42
cam on loi khuyen tu ban [nghien ] le long :)
2016-02-11 10:46:19 xin đừng quên tôi
tham khảo tại: http://yeulaptrinh.pw/32/spoj-vmdaobit/
2015-11-15 03:10:52
tham khảo nè mọi người: http://www.oni.vn/xHcjf
2015-07-28 11:48:06 [Nghien] Le Long
Ai code N2 mà vẫn 40 là do mảng phải để to hơn nhé
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.