ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Sakura and Statistics

Time limit: 1.0 second
Memory limit: 64 MB
In Tokyo, Denis met a Japanese gardener. The gardener told Denis that on some mornings one of the branches of his sakura straightened out, but in the evening it was always bent again. The branch straightens no more often than once a day, but the time when it will straighten or bend back is almost impossible to predict. The gardener has installed an automated observation system, which records the state of the branch every second. The statistics are collected and published at the gardener's web-site in the form of a picture: a white pixel denotes a bent branch and a black pixel denotes a straight branch. The observations during one day are shown in a vertical column. The picture obtained is rather strange: it's a set of vertical segments, with no more than one segment in each column. Denis said that it was unpractical to draw this picture pixel-wise. It will be more efficient to draw it by means of rectangles, for example, in JavaScript. Naturally, the gardener asked Denis to write a program that would draw the picture showing the statistics. Denis will cope with the JavaScript program himself, you only have to find the minimal set of rectangles whose union coincides with the initial picture.


The first line contains the vertical and horizontal dimensions of the picture: N and M (1 ≤ NM ≤ 50). The following lines contain the picture itself: in each of N lines there are M symbols. A black pixel is denoted by 1 and a white pixel is denoted by 0.


In the first line output the number of the rectangles. Then output the coordinates of their opposite corners. Assume that the OX axis is directed downward and the OY axis is directed to the right. If there are several solutions with the minimal number of rectangles, then output any of the solutions.


3 3
1 2 3 2
2 1 2 3
4 5
2 1 2 3
3 1 3 2
2 1 4 1
3 4 3 4
Problem Author: Sergey Pupyrev
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007
To submit the solution for this problem go to the Problem set: 1548. Sakura and Statistics