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

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

Ограничение времени: 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, Четвертьфинал Восточного подрегиона