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

NEERC 2008, Четвертьфинал Восточного подрегиона

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

A. Абстракционизм в массы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— A я никогда больше больше не буду рисовать, — ответил Незнайка, — Рисуешь, рисуешь, а никто даже спасибо не скажет, все только ругаются.
Великий художник-абстракционист Герман Брукс придумал новый стиль в живописи — бактографию. И что же это за стиль, спросите вы. А все очень просто: теперь каждая картина — живая, в буквальном смысле этого слова. Герман рисует бактериями.
Такая картина — настоящее произведение искусства. Видели бы вы это завораживающее зрелище, переливающееся двумя, а то и тремя сотнями разных оттенков. Но как же показать это чудо простым людям? Фотография или видео просто неспособны передать всю гамму красок, а музея у Германа пока еще нет (не нравятся новаторские идеи современным хранителям культуры, куда уж с ними спорить). К тому же подробно рисунок можно рассмотреть только под микроскопом. В конце концов было решено скопировать несколько особо удачных картин в тысячах экземпляров и продавать в качестве сувениров. Однако возникла проблема. Сам Герман, как настоящий творец, копировать не желает, а биоинженеры, нанятые Германом, в один голос заявляют, что можно сделать копию, только если знать четкую последовательность, в которой полотно заселяли бактериями. Ваша задача — восстановить эту последовательность.
Для решения этой задачи биоинженеры сообщили следующую информацию:
  • Законченная картина представляет собой прямоугольный холст, разделенный на одинаковые квадратные клетки, каждая из которых заселена несколькими бактериями.
  • Перед рисованием холст обязательно дезинфицируется, все его клетки пусты и не содержат бактерий.
  • В каждой клетке холста может быть не более четырех бактерий.
  • Процесс рисования заключается в том, что биоинженеры поочередно селят в свободные клетки холста по одной бактерии, при этом в каждой из соседних заселенных клеток (сверху, снизу, справа, слева) количество бактерий увеличивается на одну. Если в некоторой клетке стало 5 бактерий, то из-за перенаселения 4 из них погибают.
  • Поселить бактерию в уже заселенную клетку невозможно, ибо это приводит к непредсказуемой цепной реакции, портящей все полотно.

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

Первая строка содержит числа n и m — размеры картины Германа (1 ≤ n, m ≤ 20). Далее описывается сама картина в виде таблицы из n строк по m чисел, где в каждой ячейке записано количество бактерий в соответствующей клетке картины — целое число от 1 до 4.

Результат

В случае если получить исходную картину процедурой, доступной биоинженерам, невозможно, вывести единственное слово «No». Если же вам удалось найти какую-либо последовательность, позволяющую создать копию шедевра Германа, то выведите в первой строке «Yes», а в следующих строках саму последовательность: по два числа в каждой строке — номер строки и номер стоблца заселяемой клетки картины.

Пример

исходные данныерезультат
3 3
2 2 1
3 1 3
1 2 2
Yes
2 2
2 1
1 1
1 2
2 3
1 3
3 3
3 2
3 1
Автор задачи: Евгений Крохалев
Источник задачи: NEERC 2008, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1649. Абстракционизм в массы