ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Сакура и статистика

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В Токио Денис познакомился с японским цветоводом. Цветовод рассказал, что у его сакуры один из побегов утром иногда распрямляется, а к вечеру всегда снова склоняется вниз. Распрямляется побег не более одного раза в день, но время, когда он распрямится или согнется обратно, почти невозможно предсказать. С помощью автоматической системы слежения, которая каждую секунду отмечает состояние побега, цветовод собирает статистику и публикует её на своем сайте. Статистика публикуется в виде картинки: белый пиксель означает согнутый побег, черный — распрямившийся, показания одного дня записываются в столбик сверху вниз. Получается довольно странная картинка — набор вертикальных отрезков, не более одного в столбце. Денис сказал, что рисовать такую картинку попиксельно нерационально, эффективнее будет отрисовывать её с помощью прямоугольников, например, в JavaScript. Естественно, цветовод попросил Дениса написать программу, которая сама рисует картинку со статистикой. C программой на JavaScript Денис справится сам, а вам надо найти минимальное множество прямоугольников, объединение которых совпадает с исходной картинкой.

Исходные данные

Первая строка содержит N и M — размеры картинки по вертикали и горизонтали соответственно (1 ≤ NM ≤ 50). Последующие строки содержат саму битовую картинку. Каждая из следующих N строк содержит по M символов. Символом 1 обозначен черный пиксель, символом 0 — белый.

Результат

В первой строке выведите количество найденных прямоугольников. В следующих строках выведите координаты противоположных углов этих прямоугольников. Считаем, что ось OX направлена вниз, OY — вправо. Если оптимальных решений несколько, выведите любое из них.

Примеры

исходные данныерезультат
3 3
010
111
010
2
1 2 3 2
2 1 2 3
4 5
00000
11100
11010
10000
4
2 1 2 3
3 1 3 2
2 1 4 1
3 4 3 4
Автор задачи: Сергей Пупырев
Источник задачи: XI командный чемпионат Урала по спортивному программированию, Екатеринбург, 21 апреля 2007 г
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1548. Сакура и статистика